1. 基本介紹

樹結構多種多樣，但是最常用的還是二叉樹。二叉樹中每個節點最多有兩個子節點，這兩個節點分別是左子節點和右子節點。注意：不要求都有兩個子節點，可以只有左子節點，也可以只有右子節點。

 

2. 二叉樹的存儲

2.1. 鏈式存儲法

每個節點至少有三個字段，其中一個存儲數據，另外兩個是指向左右子節點的指針。這種存儲方式比較常用，大部分二叉樹代碼都是通過這種結構來實現的。

 

2.2. 數組存儲法

我們把根節點存儲在下標 i=1 的位置，它的左子節點存儲在下標為 2 * i 的位置，右子節點存儲在下標為 2*i+1 的位置。以此類推，B 節點、C 節點的左右子節點都按照這種規律進行存儲，最終如下圖所示。

綜上，如果節點 X 存儲在數組中下標為 i 的位置，那么下標為 2*i 的位置存儲的就是它的左子節點，下標為 2*i+1 的位置存儲的就是它的右子節點。反過來，i/2 的位置存儲的就是它的父節點。一般情況下，為了方便計算，根節點會被存儲在下標為 1 的位置。

 

通過上述可以看到，針對一般樹來說，使用數組的方式存儲樹會浪費比較多的存儲空間。但是針對下文會提到的滿二叉樹或者完全二叉樹來說，數組存儲的方式是最節省內存的一種方式。因為數組存儲時，不需要再存儲額外的左右子節點的指針。

3. 二叉樹的遍歷

二叉樹的遍歷就是將二叉樹中的所有節點遍歷打印出來。經典的方法有三種，前序遍歷、中序遍歷和后序遍歷，還可以按層遍歷（個人理解的按層遍歷其實就是按照圖的廣度優先遍歷方法來進行遍歷）。

前、中、后是根據節點被打印的先后來進行區分的：前序就是先打印節點本身，之后再打印它的左子樹，最后打印它的右子樹；中序就是先打印節點的左子樹，再打印節點本身，最后打印右子樹，即把節點放中間的位置輸出；后序就是先打印節點的左子樹，再打印節點的右子樹，最后打印節點本身。如下圖所示

 

按層遍歷類似于圖的廣度優先遍歷，先打印第一層的節點，之后再依次打印第二層的節點，以此類推。

 

3.1. 代碼實現

實際上，二叉樹的前、中、后序遍歷是一個遞歸的過程。比如，前序遍歷，其實就是先打印根節點，然后遞歸遍歷左子樹，最后遞歸遍歷右子樹。遞歸遍歷左右子樹其實就跟遍歷根節點的方法一樣。下面先寫出這三者遍歷的遞推公式：

前序遍歷的遞推公式：
preOrder(r) = print r ---> preOrder(r->left) ---> preOrder(r->right)

中序遍歷的遞推公式：
inOrder(r) = inOrder(r--->left) ---> print r ---> inOrder(r->right)

后序遍歷的遞推公式：
postOrder(r) = postOrder(r->left) ---> postOrder(r->right) --->print r

之后將遞推公式轉化為代碼如下所示：

/**
 * 前序遍歷
 */
public void preOrder(Node tree) {
    if (tree == null) {
        return;
    }

    System.out.print(tree.data + "  ");

    preOrder(tree.left);

    preOrder(tree.right);
}

/**
 * 中序遍歷
 */
public void inOrder(Node tree) {
    if (tree == null) {
        return;
    }

    inOrder(tree.left);

    System.out.print(tree.data + "  ");

    inOrder(tree.right);
}

/**
 * 后序遍歷
 */
public void postOrder(Node tree) {
    if (tree == null) {
        return;
    }

    postOrder(tree.left);

    postOrder(tree.right);

    System.out.print(tree.data + "  ");
}

★  

遞歸代碼的關鍵，在于寫出遞推公式。而遞推公式的關鍵在于，A 問題可以被拆解成 B、C 兩個問題。假設要解決 A 問題，那么假設 B、C 問題已經解決了。那么在 B、C 已經解決的提前下，看如何利用 B、C 來解決 A 。千萬不要模擬計算機一層一層想下去，否則你就會發現你自己都不知道在哪了。

”  

下面是按層遍歷的代碼，按層遍歷需要用到隊列的入隊和出隊等操作。先將根節點放入到隊列中，然后循環從隊列中取節點（出隊），再將該節點的左右子節點入隊。出隊的順序就是層次遍歷的結果。

/**
 * 層次遍歷
 */
public void BFSOrder(Node tree) {
    if (tree == null) {
        return;
    }

    Queue<Node> queue = new LinkedList<>();
    Node temp = null;
    queue.offer(tree);
    while (!queue.isEmpty()) {
        temp = queue.poll();
        System.out.print(temp.data + "  ");
        if (temp.left != null) {
            queue.offer(temp.left);
        }

        if (temp.right != null) {
            queue.offer(temp.right);
        }
    }
}

★  

完整的代碼可查看 github 倉庫 https://github.com/DawnGuoDev/algos ，這個倉庫將主要包含常用數據結構及其基本操作的手寫實現（Java），也會包含常用算法思想經典例題的實現（Java）。在程序鍋找到工作之前，這個倉庫將會保持更新狀態，在此之間學到的關于數據結構和算法的知識或者實現也都會往里面 commit，所以趕緊來 star 哦。

”  

3.2. 時間復雜度

遍歷過程中的次數就是訪問所有節點的所需的次數，而每個節點最多被訪問兩次，因此遍歷的時間復雜度是跟節點的個數 n 成正比的，即遍歷的時間復雜度是 O(n)。

4. 特殊的二叉樹

4.1. 滿二叉樹

滿二叉樹是一種特殊的二叉樹，而且還是完全二叉樹的一種特殊情況。如上圖編號 2 的那棵樹所示，葉子節點全在底層，除了葉子節點之外，每個節點都有左右兩個子節點。

4.2. 完全二叉樹

完全二叉樹也是一種特殊的二叉樹。如上圖編號 3 的那棵樹所示，葉子節點都在最底下兩層，最后一層的葉子節點都靠左排列，并且除了最后一層，其他層的節點個數都達到最大。

 

完全二叉樹的特征使得它可以使用數組就可以很好地存儲數據。完全二叉樹要求最后一層的葉子節點靠左排列也是因為如此。

4.2.1. 完全二叉樹的存儲

• 鏈式存儲

  就是上面提到的那種方式。

• 數組存儲

  完全二叉樹使用數組存儲時，如下圖所示。我們發現使用數組來存儲完全二叉樹是一種很節省內存的方式。這也是完全二叉樹被作為一種特殊樹的原因，也是完全二叉樹要求最后一層的子節點必須都靠左的原因。

  在講解堆或者堆排序的時候，堆其實也是一種完全二叉樹，最常用的存儲方式就是數組。