原创

用Java实现一颗简单的二叉树

温馨提示:
本文最后更新于 2018年06月14日,已超过 2,104 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

什么是二叉树?

实现一颗简单的二叉树

TreeNode

二叉树的结点。

package com.lzhpo.twotree;

/**
 * 二叉树
 *
 * <p>
 * Create By IntelliJ IDEA
 * Author:lzhpo
 * </p>
 */
public class TreeNode {

    //节点的权
    int value;
    //左儿子
    TreeNode leftNode;
    //右儿子
    TreeNode rightNode;

    /**
     * 二叉树的创建
     */
    //构造方法,传入一个值
    public TreeNode(int value) {
        this.value = value;
    }

    //设置左儿子
    public void setlNode(TreeNode lNode) {
        this.leftNode = lNode;
    }

    //设置右儿子
    public void setrNode(TreeNode rNode) {
        this.rightNode = rNode;
    }


    /**
     * 二叉树的遍历
     */
    //前序遍历(根,左,右)
    public void frontShow() {
        //先遍历当前节点(根节点);
        System.out.print(value);
        //左节点
        if(leftNode!=null)
        {
            leftNode.frontShow();
        }
        //右节点
        if(rightNode!=null)
        {
            rightNode.frontShow();
        }

    }
    //中序遍历(左,根,右)
    public void midShow() {
        //先遍历左节点
        if(leftNode!=null)
        {
            leftNode.midShow();
        }
        //在遍历当前节点(根节点);
        System.out.print(value);
        //最后右节点
        if(rightNode!=null)
        {
            rightNode.midShow();
        }

    }
    //后序遍历(左,右,根)
    public void afterShow() {
        //先左节点
        if(leftNode!=null)
        {
            leftNode.afterShow();
        }
        //在右节点
        if(rightNode!=null)
        {
            rightNode.afterShow();
        }
        //最后遍历当前节点(根节点);
        System.out.print(value);
    }

    //设置左孩子
    public void setleftNode(TreeNode lNode) {
        this.leftNode = lNode;
    }
    //设置右孩子
    public void setrightNode(TreeNode rNode) {
        this.rightNode = rNode;
    }

    /**
     * 二叉树的查找
     */
    //前序查找
    public TreeNode frontSearch(int i) {

        TreeNode target=null;
        //对比当前节点的值
        if(this.value==i)
        {
            return this;
            //当前节点中的值不是要查找的
        }else {
            //查找左节点
            if(leftNode!=null)
            {
                //有可能可以查到,有可能查找不到,查不到的话,target还是null
                target=leftNode.frontSearch(i);
            }
            //如果不为空,则查找成功
            if(target!=null) {
                return target;
            }
            //查找右节点
            if(rightNode!=null)
            {
                target=rightNode.frontSearch(i);
            }
        }
        return target;

    }

    /**
     * 二叉树的删除
     */
    //删除二叉树的子树
    public void delete(int i) {
        TreeNode parent=this;
        //判断左孩子
        if(parent.leftNode!=null&&parent.leftNode.value==i)
        {
            parent.leftNode=null;
            return;
        }
        //判断右孩子
        if(parent.rightNode!=null&&parent.rightNode.value==i)
        {
            parent.rightNode=null;
            return;
        }
        //如果都不是,递归检查并删除左孩子
        parent=leftNode;
        if(parent!=null)
        {
            parent.delete(i);
        }
        //递归检查并删除右孩子
        parent=rightNode;
        if(parent!=null)
        {
            parent.delete(i);
        }

    }

}

BinaryTree

实现二叉树的相关简单操作。

package com.lzhpo.twotree;

/**
 * <p>
 * Create By IntelliJ IDEA
 * Author:lzhpo
 * </p>
 */
public class BinaryTree {

    //根节点
    TreeNode root;

    /**
     * 二叉树的创建
     */
    //获取根节点
    public TreeNode getRoot() {
        return root;
    }
    //设置根节点
    public void setRoot(TreeNode root) {
        this.root = root;
    }

    /**
     * 二叉树的遍历
     */
    //前序遍历
    public void frontShow()
    {
        if(root!=null) {
            root.frontShow();
        }else
        {
            System.out.println("此二叉树为空");

        }
    }
    //中序遍历
    public void midShow()
    {
        if(root!=null) {
            root.midShow();
        }else
        {
            System.out.println("此二叉树为空");

        }
    }
    //后序遍历
    public void afterShow()
    {
        if(root!=null) {
            root.afterShow();
        }else
        {
            System.out.println("此二叉树为空");

        }
    }

    /**
     * 二叉树的查找
     * @param i
     * @return
     */
    //前序查找
    public  TreeNode frontSearch(int i) {

        return root.frontSearch(i);
    }

    /**
     * 二叉树的删除
     * @param i
     */
    public void delete(int i) {
        if(root.value==i)
        {
            root=null;
        }else {
            root.delete(i);
        }

    }

}

TestBinaryTree

main方法。

package com.lzhpo.twotree;

/**
 * <p>
 * Create By IntelliJ IDEA
 * Author:lzhpo
 * </p>
 */
public class TestBinaryTree {
    public static void main(String[] args) {

        /**
         * 创建二叉树
         */
        //创建一棵树
        BinaryTree binaryTree = new BinaryTree();
        //创建一个根节点
        TreeNode root = new TreeNode(1);
        //把根节点赋给树
        binaryTree.setRoot(root);
        //创建两个节点
        TreeNode rootL = new TreeNode(2);
        TreeNode rootR = new TreeNode(3);
        //把心创建的节点设置为根节点的子节点
        root.setlNode(rootL);
        root.setrNode(rootR);

        //为第二层的节点创建子节点
        rootL.setleftNode(new TreeNode(4));
        rootL.setrightNode(new TreeNode(5));
        rootR.setleftNode(new TreeNode(6));
        rootR.setrightNode(new TreeNode(7));

        /**
         * 遍历二叉树
         */
        System.out.println("======================二叉树的遍历======================");
        //1.前序遍历(根,左,右)
        System.out.println("此二叉树的前序遍历为:");
        binaryTree.frontShow();
        System.out.println();
        System.out.println("此二叉树的中序遍历为:");
        binaryTree.midShow();
        System.out.println();
        System.out.println("此二叉树的后序遍历为:");
        binaryTree.afterShow();

        /**
         * 二叉树的查找
         */
        System.out.println("======================二叉树的查找======================");
        TreeNode result = binaryTree.frontSearch(9);
        System.out.println(result);

        /**
         * 二叉树删除
         */
        System.out.println("======================二叉树的删除======================");
        binaryTree.delete(2);
        binaryTree.frontShow();
    }
}
本文目录