摘要：二叉樹相關問題靜態創建二叉樹首先建立一個樹節點，節點有值，左節點和右節點張夢楠樹的節點類想要創建的二叉樹創建二叉樹這樣一顆二叉樹就創建完成了樹的遍歷案例樹先序遍歷先遍得到根節點，然后是左節點，最后是右節點中序遍歷先得到左節點，然后是根節點，

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