二叉樹(shù)就是這么簡(jiǎn)單

Cruise_Chan 發(fā)布于2019-08-19 10:43 / 3110人閱讀

前言

只有光頭才能變強(qiáng)。

文本已收錄至我的GitHub倉(cāng)庫(kù)，歡迎Star：https://github.com/ZhongFuCheng3y/3y

一、二叉樹(shù)就是這么簡(jiǎn)單

本文撇開(kāi)一些非?？酀?、難以理解的概念來(lái)講講二叉樹(shù)，僅入門(mén)觀看(或復(fù)習(xí))....

首先，我們來(lái)講講什么是樹(shù)：

樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，相對(duì)于線性的數(shù)據(jù)結(jié)構(gòu)(鏈表、數(shù)組)而言，樹(shù)的平均運(yùn)行時(shí)間更短(往往與樹(shù)相關(guān)的排序時(shí)間復(fù)雜度都不會(huì)高)

在現(xiàn)實(shí)生活中，我們一般的樹(shù)長(zhǎng)這個(gè)樣子的：

但是在編程的世界中，我們一般把樹(shù)“倒”過(guò)來(lái)看，這樣容易我們分析：

一般的樹(shù)是有很多很多個(gè)分支的，分支下又有很多很多個(gè)分支，如果在程序中研究這個(gè)會(huì)非常麻煩。因?yàn)楸緛?lái)樹(shù)就是非線性的，而我們計(jì)算機(jī)的內(nèi)存是線性存儲(chǔ)的，太過(guò)復(fù)雜的話我們無(wú)法設(shè)計(jì)出來(lái)的。

因此，我們先來(lái)研究簡(jiǎn)單又經(jīng)常用的---> 二叉樹(shù)

1.1樹(shù)的一些概念

我就拿上面的圖來(lái)進(jìn)行畫(huà)來(lái)講解了：

二叉樹(shù)的意思就是說(shuō)：每個(gè)節(jié)點(diǎn)不能多于有兩個(gè)兒子，上面的圖就是一顆二叉樹(shù)。

一棵樹(shù)至少會(huì)有一個(gè)節(jié)點(diǎn)(根節(jié)點(diǎn))

樹(shù)由節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)是這樣的：

因此，我們定義樹(shù)的時(shí)候往往是->定義節(jié)點(diǎn)->節(jié)點(diǎn)連接起來(lái)就成了樹(shù)，而節(jié)點(diǎn)的定義就是：一個(gè)數(shù)據(jù)、兩個(gè)指針(如果有節(jié)點(diǎn)就指向節(jié)點(diǎn)、沒(méi)有節(jié)點(diǎn)就指向null)

1.2靜態(tài)創(chuàng)建二叉樹(shù)

上面說(shuō)了，樹(shù)是由若干個(gè)節(jié)點(diǎn)組成，節(jié)點(diǎn)連接起來(lái)就成了樹(shù)，而節(jié)點(diǎn)由一個(gè)數(shù)據(jù)、兩個(gè)指針組成

因此，創(chuàng)建樹(shù)實(shí)際上就是創(chuàng)建節(jié)點(diǎn)，然后連接節(jié)點(diǎn)

首先，使用Java類定義節(jié)點(diǎn)：


public class TreeNode {

    // 左節(jié)點(diǎn)(兒子)
    private TreeNode lefTreeNode;
    
    // 右節(jié)點(diǎn)(兒子)
    private TreeNode rightNode;
    
    // 數(shù)據(jù)
    private int value;
    

}

下面我們就拿這個(gè)二叉樹(shù)為例來(lái)構(gòu)建吧：

為了方便構(gòu)建，我就給了它一個(gè)帶參數(shù)的構(gòu)造方法和set、get方法了：

    public TreeNode(int value) {

        this.value = value;
    }

那么我們現(xiàn)在就創(chuàng)建了5個(gè)節(jié)點(diǎn)：


    public static void main(String[] args) {

        //根節(jié)點(diǎn)-->10
        TreeNode treeNode1 = new TreeNode(10);

        //左孩子-->9
        TreeNode treeNode2 = new TreeNode(9);

        //右孩子-->20
        TreeNode treeNode3 = new TreeNode(20);
        
        //20的左孩子-->15
        TreeNode treeNode4 = new TreeNode(15);
        
        //20的右孩子-->35
        TreeNode treeNode5 = new TreeNode(35)        
      
    }

它們目前的狀態(tài)是這樣子的：

于是下面我們?nèi)グ阉B起來(lái)：


    //根節(jié)點(diǎn)的左右孩子
    treeNode1.setLefTreeNode(treeNode2);
    treeNode1.setRightNode(treeNode3);

    //20節(jié)點(diǎn)的左右孩子
    treeNode3.setLefTreeNode(treeNode4);
    treeNode3.setRightNode(treeNode5);

連接完之后，那么我們的樹(shù)就創(chuàng)建完成了。

1.3遍歷二叉樹(shù)

上面說(shuō)我們的樹(shù)創(chuàng)建完成了，那怎么證明呢？？我們如果可以像數(shù)組一樣遍歷它(看它的數(shù)據(jù))，那就說(shuō)明它創(chuàng)建完成了～

值得說(shuō)明的是：二叉樹(shù)遍歷有三種方式

先序遍歷

先訪問(wèn)根節(jié)點(diǎn)，然后訪問(wèn)左節(jié)點(diǎn)，最后訪問(wèn)右節(jié)點(diǎn)(根->左->右)

中序遍歷

先訪問(wèn)左節(jié)點(diǎn)，然后訪問(wèn)根節(jié)點(diǎn)，最后訪問(wèn)右節(jié)點(diǎn)(左->根->右)

后序遍歷

先訪問(wèn)左節(jié)點(diǎn)，然后訪問(wèn)右節(jié)點(diǎn)，最后訪問(wèn)根節(jié)點(diǎn)(左->右->根)

以上面的二叉樹(shù)為例：

如果是先序遍歷：10->9->20->15->35

如果是中序遍歷：9->10->15->20->35

可能需要解釋地方：訪問(wèn)完10節(jié)點(diǎn)過(guò)后，去找的是20節(jié)點(diǎn)，但20下還有子節(jié)點(diǎn)，因此先訪問(wèn)的是20的左兒子15節(jié)點(diǎn)。由于15節(jié)點(diǎn)沒(méi)有兒子了。所以就返回20節(jié)點(diǎn)，訪問(wèn)20節(jié)點(diǎn)。最后訪問(wèn)35節(jié)點(diǎn)

如果是后序遍歷：9->15->35->20->10

可能需要解釋地方：先訪問(wèn)9節(jié)點(diǎn)，隨后應(yīng)該訪問(wèn)的是20節(jié)點(diǎn)，但20下還有子節(jié)點(diǎn)，因此先訪問(wèn)的是20的左兒子15節(jié)點(diǎn)。由于15節(jié)點(diǎn)沒(méi)有兒子了。所以就去訪問(wèn)35節(jié)點(diǎn)，由于35節(jié)點(diǎn)也沒(méi)有兒子了，所以返回20節(jié)點(diǎn)，最終返回10節(jié)點(diǎn)

一句話總結(jié)：先序(根->左->右)，中序(左->根->右)，后序(左->右->根)。如果訪問(wèn)有孩子的節(jié)點(diǎn)，先處理孩子的，隨后返回

無(wú)論先中后遍歷，每個(gè)節(jié)點(diǎn)的遍歷如果訪問(wèn)有孩子的節(jié)點(diǎn)，先處理孩子的(邏輯是一樣的)

因此我們很容易想到遞歸

遞歸的出口就是：當(dāng)沒(méi)有子節(jié)點(diǎn)了，就返回

因此，我們可以寫(xiě)出這樣的先序遍歷代碼：

    /**
     * 先序遍歷
     * @param rootTreeNode  根節(jié)點(diǎn)
     */
    public static void preTraverseBTree(TreeNode rootTreeNode) {

        if (rootTreeNode != null) {

            //訪問(wèn)根節(jié)點(diǎn)
            System.out.println(rootTreeNode.getValue());

            //訪問(wèn)左節(jié)點(diǎn)
            preTraverseBTree(rootTreeNode.getLefTreeNode());

            //訪問(wèn)右節(jié)點(diǎn)
            preTraverseBTree(rootTreeNode.getRightNode());
        }
    }

結(jié)果跟我們剛才說(shuō)的是一樣的：

我們?cè)儆?strong>中序遍歷調(diào)用一遍吧：

    /**
     * 中序遍歷
     * @param rootTreeNode  根節(jié)點(diǎn)
     */
    public static void inTraverseBTree(TreeNode rootTreeNode) {

        if (rootTreeNode != null) {

            //訪問(wèn)左節(jié)點(diǎn)
            inTraverseBTree(rootTreeNode.getLefTreeNode());

            //訪問(wèn)根節(jié)點(diǎn)
            System.out.println(rootTreeNode.getValue());

            //訪問(wèn)右節(jié)點(diǎn)
            inTraverseBTree(rootTreeNode.getRightNode());
        }
    }

結(jié)果跟我們剛才說(shuō)的是一樣的：

有意思的是：通過(guò)先序和中序或者中序和后序我們可以還原出原始的二叉樹(shù)，但是通過(guò)先序和后序是無(wú)法還原出原始的二叉樹(shù)的

也就是說(shuō)：通過(guò)中序和先序或者中序和后序我們就可以確定一顆二叉樹(shù)了！

二、動(dòng)態(tài)創(chuàng)建二叉樹(shù)

上面我們是手動(dòng)創(chuàng)建二叉樹(shù)的，一般地：都是給出一個(gè)數(shù)組給你，讓你將數(shù)組變成一個(gè)二叉樹(shù)，此時(shí)就需要我們動(dòng)態(tài)創(chuàng)建二叉樹(shù)了。

二叉樹(shù)中還有一種特殊的二叉樹(shù)：二叉查找樹(shù)(binary search tree)

定義：當(dāng)前根節(jié)點(diǎn)的左邊全部比根節(jié)點(diǎn)小，當(dāng)前根節(jié)點(diǎn)的右邊全部比根節(jié)點(diǎn)大。

明眼人可以看出，這對(duì)我們來(lái)找一個(gè)數(shù)是非常方便快捷的

往往我們動(dòng)態(tài)創(chuàng)建二叉樹(shù)都是創(chuàng)建二叉查找樹(shù)

2.1動(dòng)態(tài)創(chuàng)建二叉樹(shù)體驗(yàn)

假設(shè)我們有一個(gè)數(shù)組：int[] arrays = {3, 2, 1, 4, 5};

那么創(chuàng)建二叉樹(shù)的步驟是這樣的：

首先將3作為根節(jié)點(diǎn)

隨后2進(jìn)來(lái)了，我們跟3做比較，比3小，那么放在3的左邊

隨后1進(jìn)來(lái)了，我們跟3做比較，比3小，那么放在3的左邊，此時(shí)3的左邊有2了，因此跟2比，比2小，放在2的左邊

隨后4進(jìn)來(lái)了，我們跟3做比較，比3大，那么放在3的右邊

隨后5進(jìn)來(lái)了，我們跟3做比較，比3大，那么放在3的右邊，此時(shí)3的右邊有4了，因此跟4比，比4大，放在4的右邊

那么我們的二叉查找樹(shù)就建立成功了，無(wú)論任何一顆子樹(shù)，左邊都比根要小，右邊比根要大

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

我們的代碼實(shí)現(xiàn)也很簡(jiǎn)單，如果比當(dāng)前根節(jié)點(diǎn)要小，那么放到當(dāng)前根節(jié)點(diǎn)左邊，如果比當(dāng)前根節(jié)點(diǎn)要大，那么放到當(dāng)前根節(jié)點(diǎn)右邊。

因?yàn)槭莿?dòng)態(tài)創(chuàng)建的，因此我們得用一個(gè)類來(lái)表示根節(jié)點(diǎn)


public class TreeRoot {

    private TreeNode treeRoot;

    public TreeNode getTreeRoot() {
        return treeRoot;
    }

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

比較與根誰(shuí)大，大的往右邊，小的往左邊：


  /**
     * 動(dòng)態(tài)創(chuàng)建二叉查找樹(shù)
     *
     * @param treeRoot 根節(jié)點(diǎn)
     * @param value    節(jié)點(diǎn)的值
     */
    public static void createTree(TreeRoot treeRoot, int value) {


        //如果樹(shù)根為空(第一次訪問(wèn))，將第一個(gè)值作為根節(jié)點(diǎn)
        if (treeRoot.getTreeRoot() == null) {
            TreeNode treeNode = new TreeNode(value);
            treeRoot.setTreeRoot(treeNode);

        } else  {

            //當(dāng)前樹(shù)根
            TreeNode tempRoot = treeRoot.getTreeRoot();

            while (tempRoot != null) {
                //當(dāng)前值大于根值，往右邊走
                if (value > tempRoot.getValue()) {

                    //右邊沒(méi)有樹(shù)根，那就直接插入
                    if (tempRoot.getRightNode() == null) {
                        tempRoot.setRightNode(new TreeNode(value));
                        return ;
                    } else {
                        //如果右邊有樹(shù)根，到右邊的樹(shù)根去
                        tempRoot = tempRoot.getRightNode();
                    }
                } else {
                    //左沒(méi)有樹(shù)根，那就直接插入
                    if (tempRoot.getLefTreeNode() == null) {
                        tempRoot.setLefTreeNode(new TreeNode(value));

                        return;
                    } else {
                        //如果左有樹(shù)根，到左邊的樹(shù)根去
                        tempRoot = tempRoot.getLefTreeNode();
                    }
                }
            }
        }
    }

測(cè)試代碼：

    int[] arrays = {2, 3, 1, 4, 5};

    //動(dòng)態(tài)創(chuàng)建樹(shù)

    TreeRoot root = new TreeRoot();
    for (int value : arrays) {
        createTree(root, value);
    }


    //中序遍歷樹(shù)
    inTraverseBTree(root.getTreeRoot());
    System.out.println("---------------公眾號(hào)：Java3y");
    
    //先序遍歷樹(shù)
    preTraverseBTree(root.getTreeRoot());
    System.out.println("---------------公眾號(hào)：Java3y");

三、查詢二叉查找樹(shù)相關(guān) 3.1查詢樹(shù)的深度

查詢樹(shù)的深度我們可以這樣想：左邊的子樹(shù)和右邊的字?jǐn)?shù)比，誰(shuí)大就返回誰(shuí)，那么再接上根節(jié)點(diǎn)+1就可以了

    public static int getHeight(TreeNode treeNode) {

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

            //左邊的子樹(shù)深度
            int left = getHeight(treeNode.getLefTreeNode());

            //右邊的子樹(shù)深度
            int right = getHeight(treeNode.getRightNode());


            int max = left;

            if (right > max) {
                max = right;
            }
            return max + 1;
        }
    }

3.1查詢樹(shù)的最大值

從上面先序遍歷二叉查找樹(shù)的時(shí)候，細(xì)心的同學(xué)可能會(huì)發(fā)現(xiàn)：中序遍歷二叉查找樹(shù)得到的結(jié)果是排好順序的～

那么，如果我們的二叉樹(shù)不是二叉查找樹(shù)，我們要怎么查詢他的最大值呢？

可以這樣：

左邊找最大值->遞歸

右邊找最大值->遞歸


    /**
     * 找出樹(shù)的最大值
     *
     * @param rootTreeNode
     */
    public static int  getMax(TreeNode rootTreeNode) {

        if (rootTreeNode == null) {
            return -1;
        } else {
            //找出左邊的最大值
            int left = getMax(rootTreeNode.getLefTreeNode());

            //找出右邊的最大值
            int right = getMax(rootTreeNode.getRightNode());

            //與當(dāng)前根節(jié)點(diǎn)比較
            int currentRootValue = rootTreeNode.getValue();

            //假設(shè)左邊的最大
            int max = left;


            if (right > max) {
                max = right;
            }
            if (currentRootValue > max) {
                max = currentRootValue;
            }

            return max ;


        }
    }

四、最后

無(wú)論是在遍歷樹(shù)、查找深度、查找最大值都用到了遞歸，遞歸在非線性的數(shù)據(jù)結(jié)構(gòu)中是用得非常多的...

樹(shù)的應(yīng)用也非常廣泛，此篇簡(jiǎn)單地說(shuō)明了樹(shù)的數(shù)據(jù)結(jié)構(gòu)，高級(jí)的東西我也沒(méi)弄懂，可能以后用到的時(shí)候會(huì)繼續(xù)深入...

樂(lè)于輸出干貨的Java技術(shù)公眾號(hào)：Java3y。公眾號(hào)內(nèi)有200多篇原創(chuàng)技術(shù)文章、海量視頻資源、精美腦圖，不妨來(lái)關(guān)注一下！

云服務(wù)器 GPU云服務(wù)器二叉樹(shù) python二叉樹(shù) 平衡二叉樹(shù) 實(shí)現(xiàn)二叉樹(shù)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/76367.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

Cruise_Chan

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

如何選擇云虛擬主機(jī)-該怎么選擇合適自己的云虛擬主機(jī)？

閱讀 1318·2021-09-22 15:43
華為如何上傳文件到windows云主機(jī)-云主機(jī)怎么上傳程序呢？

閱讀 2526·2021-09-22 15:32
主機(jī)指的是什么-通常所說(shuō)的主機(jī)是指什么？

閱讀 4761·2021-09-22 15:11
CSS居中總結(jié)大全

閱讀 2460·2019-08-30 15:55
CSS+DIV自適應(yīng)布局

閱讀 2802·2019-08-30 15:54
浮動(dòng)定位之三列布局問(wèn)題與發(fā)現(xiàn)（下）

閱讀 1111·2019-08-30 15:44
前端面試總結(jié)——持續(xù)更新

閱讀 1298·2019-08-29 13:26
CSS 公共樣式分享

閱讀 935·2019-08-29 12:54

成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲中文字幕日韩无码

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

二叉樹(shù)就是這么簡(jiǎn)單

相關(guān)文章

堆排序就這么簡(jiǎn)單

Map集合、散列表、紅黑樹(shù)介紹

發(fā)表評(píng)論

0條評(píng)論

Cruise_Chan

男|高級(jí)講師

TA的文章

如何選擇云虛擬主機(jī)-該怎么選擇合適自己的云虛擬主機(jī)？

華為如何上傳文件到windows云主機(jī)-云主機(jī)怎么上傳程序呢？

主機(jī)指的是什么-通常所說(shuō)的主機(jī)是指什么？

CSS居中總結(jié)大全

CSS+DIV自適應(yīng)布局

浮動(dòng)定位之三列布局問(wèn)題與發(fā)現(xiàn)（下）

前端面試總結(jié)——持續(xù)更新

CSS 公共樣式分享

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

二叉樹(shù)就是這么簡(jiǎn)單

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！