二叉树相关

摘要：二叉树相关问题静态创建二叉树首先建立一个树节点，节点有值，左节点和右节点张梦楠树的节点类想要创建的二叉树创建二叉树这样一颗二叉树就创建完成了树的遍历案例树先序遍历先遍得到根节点，然后是左节点，最后是右节点中序遍历先得到左节点，然后是根节点，

1.首先建立一个树节点，节点有值，左节点和右节点

/**
 * @author 张梦楠
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: ${todo}
 * @date 2018/5/2519:27
 * @blog www.itzmn.com
 *
 * 树的节点类
 */
public class TreeNode {

    public int value;

    public TreeNode leftNode;

    public TreeNode rightNode;
    public TreeNode() {
    }
    public TreeNode(int value) {
        this.value = value;
    }

2.想要创建的二叉树

3.创建二叉树

public static void main(String args[]){
        TreeNode treeNode10 = new TreeNode(10);
        TreeNode treeNode9 = new TreeNode(9);
        TreeNode treeNode15 = new TreeNode(15);
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode13 = new TreeNode(13);
        TreeNode treeNode12 = new TreeNode(12);


        treeNode10.setLeftNode(treeNode9);
        treeNode10.setRightNode(treeNode15);

        treeNode9.setRightNode(treeNode12);

        treeNode15.setLeftNode(treeNode13);
        treeNode15.setRightNode(treeNode1);

这样一颗二叉树就创建完成了

案例树：

先序遍历：先遍得到根节点，然后是左节点，最后是右节点
10 9 12 15 13 1

中序遍历：先得到左节点，然后是根节点，最后是右节点
9 12 10 13 15 1

后序遍历： 先得到左节点，然后是右节点，最后是根节点
12 9 13 1 15 10

只需要记住，前中后是对于根节点来说的，所有遍历，都是先左后右，然后看看根节点在哪，

代码实现：

//先序遍历二叉树

    /**
     * 思路：
     *  先查找根节点，然后查找左节点，然后查找右节点
     * @param RoottreeNode 树的根节点
     */
    private static void xianxu(TreeNode RoottreeNode) {

        if (RoottreeNode!=null){
            System.out.print(RoottreeNode.getValue()+" ");
            //查找左节点
            xianxu(RoottreeNode.getLeftNode());
            //查找右节点
            xianxu(RoottreeNode.getRightNode());
        }


    }

 //中序遍历二叉树
    /**
     * 思路：
     *  先查找左节点，然后查找根节点，最后查找右节点
     * @param RoottreeNode
     */
    private static void zhongxu(TreeNode RoottreeNode) {

       if (RoottreeNode!=null){
            //查找左边的节点
           zhongxu(RoottreeNode.getLeftNode());
           //输出节点值
           System.out.print(RoottreeNode.getValue()+" ");
           //查找右节点
           zhongxu(RoottreeNode.getRightNode());

       }


    }

 //后序遍历二叉树

    /**
     * 思路：
     *  先遍历左节点，然后遍历右节点，然后输出根几点
     * @param RoottreeNode
     */
    private static void houxu(TreeNode RoottreeNode) {
        if (RoottreeNode!=null){
            houxu(RoottreeNode.getLeftNode());
            houxu(RoottreeNode.getRightNode());
            System.out.print(RoottreeNode.getValue()+" ");
        }
    }

一般而言都是给数组，然后自己实现二叉树，所以要自己动态生成二叉树
{7,1,9,3,2,6}

最终树的效果：

思路：选定一个数据为根节点，然后判断后面的数据，如果比根节点大，就放在右边，如果比根节点小，放在左边，如果右边有节点，就把右节点当做根节点，继续比较，递归，左节点同理

首先需要创建一个根节点，用来存储根节点
代码：

 *  树的根类
 */
public class TreeRoot {

    public TreeNode treeRoot;

    public TreeNode getTreeRoot() {
        return treeRoot;
    }

    public void setTreeRoot(TreeNode treeRoot) {
        this.treeRoot = treeRoot;
    }
}

代码实现：

 /**
     * 动态创建二叉查找树
     * 思路：
     *  根据根节点，如果根节点为null就创建根节点，
     *  根据传入的值，和根节点比较大小，小的放左边，大的放右边，
     *      如果左边有节点，就把左节点看成根节点重新判断，右边同理
     * @param treeRoot
     * @param value
     */
    private static void create(TreeRoot treeRoot, int value) {

        if (treeRoot.getTreeRoot()==null){//如果跟没有节点，就创建一个节点，作为树根
            treeRoot.setTreeRoot(new TreeNode(value));
        }else {
            TreeNode currtreeRoot = treeRoot.getTreeRoot();
            while (currtreeRoot!=null){

                if (currtreeRoot.getValue()>value){//如果当前数根的值大于传入的值
                    //将值放在树的左边，
                    if (currtreeRoot.getLeftNode()==null){
                        //如果树节点的左侧没有值，就直接插入
                        currtreeRoot.setLeftNode(new TreeNode(value));
                        return;
                    }else {
                        //如果节点左侧有值,就把根节点变成左侧节点，继续判断
                        currtreeRoot = currtreeRoot.getLeftNode();
                    }
                }else {
                    //如果当前根值小于传入的值，将值放在右边
                    if (currtreeRoot.getRightNode()==null){
                        currtreeRoot.setRightNode(new TreeNode(value));
                        return;
                    }else {
                        //如果右侧节点存在的话
                        currtreeRoot = currtreeRoot.getRightNode();
                    }
                }

            }


        }

    }

测试用例：加上刚刚的遍历，

public static void main(String args[]){

        int[] arrs = {7,1,9,3,2,6};
        TreeRoot treeRoot = new TreeRoot();
        for (int i:arrs){
            create(treeRoot,i);
        }
        System.out.print("先序查找：");
        xianxu(treeRoot.getTreeRoot());
        System.out.println();
        System.out.print("中序查找：");
        zhongxu(treeRoot.getTreeRoot());
        System.out.println();
        System.out.print("后序查找：");
        houxu(treeRoot.getTreeRoot());

得到二叉树的高度

代码：

 /**
     * 得到树的高度
     * @param treeRoot
     * *
     *               7
     *          1         9
     *             3
     *           2    6
     */
    private static int getHeight(TreeNode treeRoot) {

        if (treeRoot==null){
            return 0;
        }else {

            //如果节点不为空
            int left = getHeight(treeRoot.getLeftNode());
            int right = getHeight(treeRoot.getRightNode());

            if (right > left){
                return right+1;
            }
            return left+1;
        }

    }

更多详情QQ群：552113611