數(shù)據(jù)結(jié)構(gòu)與算法——二叉樹（上）

xeblog 發(fā)布于2019-08-16 16:13 / 1313人閱讀

摘要：什么是樹前面說到的幾種數(shù)據(jù)結(jié)構(gòu)都是線性的，例如鏈表棧隊列等，今天就來學習一種非線性的數(shù)據(jù)結(jié)構(gòu)樹。在上圖中的幾種二叉樹中，有兩個是比較特殊的，分別是滿二叉樹和完全二叉樹。除了使用數(shù)組存儲二叉樹外，最常用的便是使用鏈表法來儲存二叉樹了。

1. 什么是樹？

前面說到的幾種數(shù)據(jù)結(jié)構(gòu)都是線性的，例如鏈表、棧、隊列等，今天就來學習一種非線性的數(shù)據(jù)結(jié)構(gòu)——樹。先來看看幾種樹的結(jié)構(gòu)：

有沒有發(fā)現(xiàn)，其實樹這種結(jié)構(gòu)跟我們現(xiàn)實生活中的“樹”非常的相似，像上圖中的這棵“樹”，節(jié)點 A 稱作 B 和 C 的父節(jié)點，節(jié)點 B 和 C 在同一級，叫做兄弟節(jié)點。沒有父節(jié)點的 A 節(jié)點叫做根節(jié)點，沒有子節(jié)點的節(jié)點叫做葉子節(jié)點或葉節(jié)點，例如圖中的 D E F G。

樹的節(jié)點還涉及到三個概念，分別是高度、深度、層。

節(jié)點高度：節(jié)點到葉子節(jié)點的最長路徑

節(jié)點深度：根節(jié)點到這個節(jié)點所經(jīng)歷的邊的個數(shù)

節(jié)點的層：節(jié)點深度 + 1

樹的高度：根節(jié)點的高度

結(jié)合下面的圖你就能夠理解了，高度是從下到上數(shù)的，深度是從上到下數(shù)的：

2. 二叉樹

樹的形態(tài)多種多樣，但是我們平常最常用的還是二叉樹，顧名思義，二叉樹就是每個節(jié)點最多只有兩個子節(jié)點的樹。

在上圖中的幾種二叉樹中，有兩個是比較特殊的，分別是滿二叉樹和完全二叉樹。

滿二叉樹：樹的葉子節(jié)點全在最底層，并且除了葉子節(jié)點，每個節(jié)點都有左右兩個子節(jié)點，例如上圖中的樹 2。

完全二叉樹：葉子節(jié)點都在最底下兩層，最底層的節(jié)點全都靠左排列，并且除了最后一層，其他層的節(jié)點都必須有左右兩個節(jié)點，例如上圖中的樹 3。

完全二叉樹的概念有點不太好理解，你可以多思考一下，其實滿二叉樹就是完全二叉樹的一種特殊情況。完全二叉樹的這種特性是為了方便其在數(shù)組中的存儲，不至于浪費太多的內(nèi)存空間，等后面說到堆的時候你就更能理解了。
除了使用數(shù)組存儲二叉樹外，最常用的便是使用鏈表法來儲存二叉樹了。下面說到的二叉樹的遍歷便是這種存儲方法。

3. 二叉樹的遍歷

二叉樹的一種常見操作就是需要遍歷得到樹種的全部數(shù)據(jù)，最常用的遍歷方式有三種：前序遍歷、中序遍歷、后序遍歷。

前序遍歷：對于樹中的任意節(jié)點來說，先遍歷這個節(jié)點，然后遍歷這個節(jié)點的左子節(jié)點，最后遍歷這個節(jié)點的右子節(jié)點。（父左右）

中序遍歷：對于樹中的任意節(jié)點來說，先遍歷這個節(jié)點的左子節(jié)點，然后遍歷這個節(jié)點本身，最后遍歷這個節(jié)點的右子節(jié)點。（左父右）

后序遍歷：對于樹中的任意節(jié)點來說，先遍歷這個節(jié)點的左子節(jié)點，然后遍歷這個節(jié)點的右子節(jié)點，最后遍歷這個節(jié)點本身。（左右父）

其實樹的遍歷是一種很典型的遞歸操作，代碼也可以使用遞歸來實現(xiàn)，你可以看看我實現(xiàn)的代碼。

    //1.前序遍歷
    public void preOrder(Node head){
        if (head == null) return;
        System.out.print(head.getData() + "  ");
        preOrder(head.left);
        preOrder(head.right);
    }

    //2.中序遍歷
    public void midOrder(Node head){
        if (head == null) return;
        midOrder(head.left);
        System.out.print(head.getData() + "  ");
        midOrder(head.right);
    }

    //3.后序遍歷
    public void postOrder(Node head){
        if (head == null) return;
        postOrder(head.left);
        postOrder(head.right);
        System.out.print(head.getData() + "  ");
    }