摘要：二叉樹相關(guān)問題靜態(tài)創(chuàng)建二叉樹首先建立一個(gè)樹節(jié)點(diǎn)，節(jié)點(diǎn)有值，左節(jié)點(diǎn)和右節(jié)點(diǎn)張夢(mèng)楠樹的節(jié)點(diǎn)類想要?jiǎng)?chuàng)建的二叉樹創(chuàng)建二叉樹這樣一顆二叉樹就創(chuàng)建完成了樹的遍歷案例樹先序遍歷先遍得到根節(jié)點(diǎn)，然后是左節(jié)點(diǎn)，最后是右節(jié)點(diǎn)中序遍歷先得到左節(jié)點(diǎn)，然后是根節(jié)點(diǎn)，

1.首先建立一個(gè)樹節(jié)點(diǎn)，節(jié)點(diǎn)有值，左節(jié)點(diǎn)和右節(jié)點(diǎn)

/**
 * @author 張夢(mèng)楠
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: ${todo}
 * @date 2018/5/2519:27
 * @blog www.itzmn.com
 *
 * 樹的節(jié)點(diǎn)類
 */
public class TreeNode {

    public int value;

    public TreeNode leftNode;

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

2.想要?jiǎng)?chuàng)建的二叉樹

3.創(chuàng)建二叉樹

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);

這樣一顆二叉樹就創(chuàng)建完成了

案例樹：

先序遍歷：先遍得到根節(jié)點(diǎn)，然后是左節(jié)點(diǎn)，最后是右節(jié)點(diǎn)
10 9 12 15 13 1

中序遍歷：先得到左節(jié)點(diǎn)，然后是根節(jié)點(diǎn)，最后是右節(jié)點(diǎn)
9 12 10 13 15 1

后序遍歷： 先得到左節(jié)點(diǎn)，然后是右節(jié)點(diǎn)，最后是根節(jié)點(diǎn)
12 9 13 1 15 10

只需要記住，前中后是對(duì)于根節(jié)點(diǎn)來說的，所有遍歷，都是先左后右，然后看看根節(jié)點(diǎn)在哪，

代碼實(shí)現(xiàn)：

//先序遍歷二叉樹

    /**
     * 思路：
     *  先查找根節(jié)點(diǎn)，然后查找左節(jié)點(diǎn)，然后查找右節(jié)點(diǎn)
     * @param RoottreeNode 樹的根節(jié)點(diǎn)
     */
    private static void xianxu(TreeNode RoottreeNode) {

        if (RoottreeNode!=null){
            System.out.print(RoottreeNode.getValue()+" ");
            //查找左節(jié)點(diǎn)
            xianxu(RoottreeNode.getLeftNode());
            //查找右節(jié)點(diǎn)
            xianxu(RoottreeNode.getRightNode());
        }


    }

 //中序遍歷二叉樹
    /**
     * 思路：
     *  先查找左節(jié)點(diǎn)，然后查找根節(jié)點(diǎn)，最后查找右節(jié)點(diǎn)
     * @param RoottreeNode
     */
    private static void zhongxu(TreeNode RoottreeNode) {

       if (RoottreeNode!=null){
            //查找左邊的節(jié)點(diǎn)
           zhongxu(RoottreeNode.getLeftNode());
           //輸出節(jié)點(diǎn)值
           System.out.print(RoottreeNode.getValue()+" ");
           //查找右節(jié)點(diǎn)
           zhongxu(RoottreeNode.getRightNode());

       }


    }

 //后序遍歷二叉樹

    /**
     * 思路：
     *  先遍歷左節(jié)點(diǎn)，然后遍歷右節(jié)點(diǎn)，然后輸出根幾點(diǎn)
     * @param RoottreeNode
     */
    private static void houxu(TreeNode RoottreeNode) {
        if (RoottreeNode!=null){
            houxu(RoottreeNode.getLeftNode());
            houxu(RoottreeNode.getRightNode());
            System.out.print(RoottreeNode.getValue()+" ");
        }
    }

一般而言都是給數(shù)組，然后自己實(shí)現(xiàn)二叉樹，所以要自己動(dòng)態(tài)生成二叉樹
{7,1,9,3,2,6}

最終樹的效果：

思路：選定一個(gè)數(shù)據(jù)為根節(jié)點(diǎn)，然后判斷后面的數(shù)據(jù)，如果比根節(jié)點(diǎn)大，就放在右邊，如果比根節(jié)點(diǎn)小，放在左邊，如果右邊有節(jié)點(diǎn)，就把右節(jié)點(diǎn)當(dāng)做根節(jié)點(diǎn)，繼續(xù)比較，遞歸，左節(jié)點(diǎn)同理

首先需要?jiǎng)?chuàng)建一個(gè)根節(jié)點(diǎn)，用來存儲(chǔ)根節(jié)點(diǎn)
代碼：

 *  樹的根類
 */
public class TreeRoot {

    public TreeNode treeRoot;

    public TreeNode getTreeRoot() {
        return treeRoot;
    }

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

代碼實(shí)現(xiàn)：

 /**
     * 動(dòng)態(tài)創(chuàng)建二叉查找樹
     * 思路：
     *  根據(jù)根節(jié)點(diǎn)，如果根節(jié)點(diǎn)為null就創(chuàng)建根節(jié)點(diǎn)，
     *  根據(jù)傳入的值，和根節(jié)點(diǎn)比較大小，小的放左邊，大的放右邊，
     *      如果左邊有節(jié)點(diǎn)，就把左節(jié)點(diǎn)看成根節(jié)點(diǎn)重新判斷，右邊同理
     * @param treeRoot
     * @param value
     */
    private static void create(TreeRoot treeRoot, int value) {

        if (treeRoot.getTreeRoot()==null){//如果跟沒有節(jié)點(diǎn)，就創(chuàng)建一個(gè)節(jié)點(diǎn)，作為樹根
            treeRoot.setTreeRoot(new TreeNode(value));
        }else {
            TreeNode currtreeRoot = treeRoot.getTreeRoot();
            while (currtreeRoot!=null){

                if (currtreeRoot.getValue()>value){//如果當(dāng)前數(shù)根的值大于傳入的值
                    //將值放在樹的左邊，
                    if (currtreeRoot.getLeftNode()==null){
                        //如果樹節(jié)點(diǎn)的左側(cè)沒有值，就直接插入
                        currtreeRoot.setLeftNode(new TreeNode(value));
                        return;
                    }else {
                        //如果節(jié)點(diǎn)左側(cè)有值,就把根節(jié)點(diǎn)變成左側(cè)節(jié)點(diǎn)，繼續(xù)判斷
                        currtreeRoot = currtreeRoot.getLeftNode();
                    }
                }else {
                    //如果當(dāng)前根值小于傳入的值，將值放在右邊
                    if (currtreeRoot.getRightNode()==null){
                        currtreeRoot.setRightNode(new TreeNode(value));
                        return;
                    }else {
                        //如果右側(cè)節(jié)點(diǎn)存在的話
                        currtreeRoot = currtreeRoot.getRightNode();
                    }
                }

            }


        }

    }

測(cè)試用例：加上剛剛的遍歷，

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 {

            //如果節(jié)點(diǎn)不為空
            int left = getHeight(treeRoot.getLeftNode());
            int right = getHeight(treeRoot.getRightNode());

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

    }

更多詳情QQ群：552113611