前面課時我們學習了線性表、棧、隊列和數組。棧、隊列都是特殊的線性表，數組可以看成是線性表的一種推廣。根據學習，我們知道了這幾種數據結構，在對數據的增刪查操作上各有千秋。這一課時再來學習另一種從形式上看上去差異比較大的數據結構，樹，以及如何用樹和二叉樹實現對數據的增刪查的操作。 #### 樹是什么 樹是由結點和邊組成的，不存在環的一種數據結構。通過下圖，我們就可以更直觀的認識樹的結構。  樹滿足遞歸定義的特性。也就是說，如果一個數據結構是樹結構，那么剔除掉根結點后，得到的若干個子結構也是樹，通常稱作子樹。 在一棵樹中，根據結點之間層次關系的不同，對結點的稱呼也有所不同。我們來看下面這棵樹，如下圖所示: * A 結點是 B 結點和 C 結點的上級，則 A 就是 B 和 C 的父結點，B 和 C 是 A 的子結點。 * B 和 C 同時是 A 的“孩子”，則可以稱 B 和 C 互為兄弟結點。 * A 沒有父結點，則可以稱 A 為根結點。 * G、H、I、F 結點都沒有子結點，則稱 G、H、I、F 為葉子結點。  當有了一棵樹之后，還需要用深度、層來描述這棵樹中結點的位置。結點的層次從根結點算起，根為第一層，根的“孩子”為第二層，根的“孩子”的“孩子”為第三層，依此類推。樹中結點的最大層次數，就是這棵樹的樹深（稱為深度，也稱為高度）。如下圖所示，就是一棵深度為 4 的樹。  #### 二叉樹是什么 在樹的大家族中，有一種被高頻使用的特殊樹，它就是二叉樹。在二叉樹中，每個結點最多有兩個分支，即每個結點最多有兩個子結點，分別稱作左子結點和右子結點。 在二叉樹中，有下面兩個特殊的類型，如下圖所示： * 滿二叉樹，定義為除了葉子結點外，所有結點都有 2 個子結點。 * 完全二叉樹，定義為除了最后一層以外，其他層的結點個數都達到最大，并且最后一層的葉子結點都靠左排列。  你可能會困惑，完全二叉樹看上去并不完全，但為什么這樣稱呼它呢？這其實和二叉樹的存儲有關系。存儲二叉樹有兩種辦法，一種是基于指針的鏈式存儲法，另一種是基于數組的順序存儲法。 * 鏈式存儲法，也就是像鏈表一樣，每個結點有三個字段，一個存儲數據，另外兩個分別存放指向左右子結點的指針，如下圖所示：  * 順序存儲法，就是按照規律把結點存放在數組里，如下圖所示，為了方便計算，我們會約定把根結點放在下標為 1 的位置。隨后，B 結點存放在下標為 2 的位置，C 結點存放在下標為 3 的位置，依次類推。  根據這種存儲方法，我們可以發現如果結點 X 的下標為 i，那么 X 的左子結點總是存放在 2 * i 的位置，X 的右子結點總是存放在 2 * i + 1 的位置。 之所以稱為完全二叉樹，是從存儲空間利用效率的視角來看的。對于一棵完全二叉樹而言，僅僅浪費了下標為 0 的存儲位置。而如果是一棵非完全二叉樹，則會浪費大量的存儲空間。 我們來看如下圖所示的非完全二叉樹，它既需要保留出 5 和 6 的位置。同時，還需要保留 5 的兩個子結點 10 和 11 的位置，以及 6 的兩個子結點 12 和 13 的位置。這樣的二叉樹，沒有完全利用好數組的存儲空間。  #### 樹的基本操作 接下來，我們以二叉樹為例介紹樹的操作，其他類型的樹的操作與二叉樹基本相似。 可以發現，我們以前學到的數據結構都是“一對一”的關系，即前面的數據只跟下面的一個數據產生了連接關系，例如鏈表、棧、隊列等。而樹結構則是“一對多”的關系，即前面的父結點，跟下面若干個子結點產生了連接關系。 在前面的課時中我們提到過，要在數據結構中，查找具有某個數值特性的數據需要遍歷每一條數據。這在“一對一”的結構中，直接按順序訪問就好了。可是，樹是“一對多”的關系，那么我們該如何進行數據的遍歷，才能保證每條數據都會被訪問一次且沒有遺漏呢？我們只有解決了遍歷問題，才能通過樹來進行數據的增刪查操作。 其實，遍歷一棵樹，有非常經典的三種方法，分別是前序遍歷、中序遍歷、后序遍歷。這里的序指的是父結點的遍歷順序，前序就是先遍歷父結點，中序就是中間遍歷父結點，后序就是最后遍歷父結點。不管哪種遍歷，都是通過遞歸調用完成的。如下圖所示： * 前序遍歷，對樹中的任意結點來說，先打印這個結點，然后前序遍歷它的左子樹，最后前序遍歷它的右子樹。 * 中序遍歷，對樹中的任意結點來說，先中序遍歷它的左子樹，然后打印這個結點，最后中序遍歷它的右子樹。 * 后序遍歷，對樹中的任意結點來說，先后序遍歷它的左子樹，然后后序遍歷它的右子樹，最后打印它本身。  通過前面的介紹，相信你已經了解了二叉樹的三種遍歷方式，下面我們再來分析一下代碼的實現過程，如下所示： ``` // 先序遍歷 public static void preOrderTraverse(Node node) { if (node == null) return; System.out.print(node.data + " "); preOrderTraverse(node.left); preOrderTraverse(node.right); } // 中序遍歷 public static void inOrderTraverse(Node node) { if (node == null) return; inOrderTraverse(node.left); System.out.print(node.data + " "); inOrderTraverse(node.right); } // 后序遍歷 public static void postOrderTraverse(Node node) { if (node == null) return; postOrderTraverse(node.left); postOrderTraverse(node.right); System.out.print(node.data + " "); } ``` 不難發現，二叉樹遍歷過程中，每個結點都被訪問了一次，其時間復雜度是 O(n)。接著，在找到位置后，執行增加和刪除數據的操作時，我們只需要通過指針建立連接關系就可以了。對于沒有任何特殊性質的二叉樹而言，拋開遍歷的時間復雜度以外，真正執行增加和刪除操作的時間復雜度是 O(1)。樹數據的查找操作和鏈表一樣，都需要遍歷每一個數據去判斷，所以時間復雜度是 O(n)。 我們上面講到二叉樹的增刪查操作很普通，時間復雜度與鏈表并沒有太多差別。但當二叉樹具備一些特性的時候，則可以利用這些特性實現時間復雜度的降低。接下來，我們詳細介紹二叉查找樹的特性。 #### 二叉查找樹的特性 二叉查找樹（也稱作二叉搜索樹）具備以下幾個的特性： * 在二叉查找樹中的任意一個結點，其左子樹中的每個結點的值，都要小于這個結點的值。 * 在二叉查找樹中的任意一個結點，其右子樹中每個結點的值，都要大于這個結點的值。 * 在二叉查找樹中，會盡可能規避兩個結點數值相等的情況。 * 對二叉查找樹進行中序遍歷，就可以輸出一個從小到大的有序數據隊列。如下圖所示，中序遍歷的結果就是 10、13、15、16、20、21、22、26。  #### 二叉查找樹的查找操作 在利用二叉查找樹執行查找操作時，我們可以進行以下判斷： * 首先判斷根結點是否等于要查找的數據，如果是就返回。 * 如果根結點大于要查找的數據，就在左子樹中遞歸執行查找動作，直到葉子結點。 * 如果根結點小于要查找的數據，就在右子樹中遞歸執行查找動作，直到葉子結點。 這樣的“二分查找”所消耗的時間復雜度就可以降低為 O(logn)。關于二分查找，我們會在后續的分治法一講中詳細講述。 #### 二叉查找樹的插入操作 在二叉查找樹執行插入操作也很簡單。從根結點開始，如果要插入的數據比根結點的數據大，且根結點的右子結點不為空，則在根結點的右子樹中繼續嘗試執行插入操作。直到找到為空的子結點執行插入動作。 如下圖所示，如果要插入數據 X 的值為 14，則需要判斷 X 與根結點的大小關系： * 由于 14 小于 16，則聚焦在其左子樹，繼續判斷 X 與 13 的關系。 * 由于 14 大于 13，則聚焦在其右子樹，繼續判斷 X 與15 的關系。 * 由于 14 小于 15，則聚焦在其左子樹。 因為此時左子樹為空，則直接通過指針建立 15 結點的左指針指向結點 X 的關系，就完成了插入動作。  二叉查找樹插入數據的時間復雜度是 O(logn)。但這并不意味著它比普通二叉樹要復雜。原因在于這里的時間復雜度更多是消耗在了遍歷數據去找到查找位置上，真正執行插入動作的時間復雜度仍然是 O(1)。 二叉查找樹的刪除操作會比較復雜，這是因為刪除完某個結點后的樹，仍然要滿足二叉查找樹的性質。我們分為下面三種情況討論。 * 情況一，如果要刪除的結點是某個葉子結點，則直接刪除，將其父結點指針指向 null 即可。  * 情況二，如果要刪除的結點只有一個子結點，只需要將其父結點指向的子結點的指針換成其子結點的指針即可。  * 情況三，如果要刪除的結點有兩個子結點，則有兩種可行的操作方式。 第一種，找到這個結點的左子樹中最大的結點，替換要刪除的結點。  第二種，找到這個結點的右子樹中最小的結點，替換要刪除的結點。  #### 樹的案例 我們來看一道例題: 輸入一個字符串，判斷它在已有的字符串集合中是否出現過?（假設集合中沒有某個字符串與另一個字符串擁有共同前綴且完全包含的特殊情況，例如 deep 和 dee。）如，已有字符串集合包含 6 個字符串分別為，cat, car, city, dog,door, deep。輸入 cat，輸出 true；輸入 home，輸出 false。 我們假設采用最暴力的辦法，估算一下時間復雜度。假設字符串集合包含了 n 個字符串，其中的字符串平均長度為 m。那么新來的一個字符串，需要與每個字符串的每個字符進行匹配。則時間復雜度為 O(nm)。 但在 nm 的復雜度中，顯然存在很多的無效匹配。例如，輸入 home 時，6 個字符串都沒有 h 開頭的，則不需要進行后續的匹配。因此，如果可以通過對字符前綴進行處理，就可以最大限度地減少無謂的字符串比較，從而提高查詢效率。這就是“用空間換時間”的思想，再利用共同前綴來提高查詢效率。 其實，這個問題利用樹結構也可以完成。我們對字符串建立一個的樹結構，如下圖所示，它將字符串集合的前綴進行合并，每個根結點到葉子結點的鏈條就是一個字符串。  這個樹結構也稱作 Trie 樹，或字典樹。它具有三個特點： * 第一，根結點不包含字符； * 第二，除根結點外每一個結點都只包含一個字符； * 第三，從根結點到某一葉子結點，路徑上經過的字符連接起來，即為集合中的某個字符串。 這個問題的解法可以拆解為以下兩個步驟： * 第一步，根據候選字符串集合，建立字典樹。這需要使用數據插入的動作。 * 第二步，對于一個輸入字符串，判斷它能否在這個樹結構中走到葉子結點。如果能，則出現過。  #### 總結 本課時的內容圍繞著不同種類樹的原理、二叉樹對于數據的增刪查操作展開。要想利用二叉樹實現增刪查操作，你需要熟練掌握二叉樹的三種遍歷方式。遍歷的時間復雜度是 O(n)。有了遍歷方式之后，你可以完成在指定位置的數據增刪操作。增刪操作的時間復雜度都是 O(1)。 對于查找操作，如果是普通二叉樹，則查找的時間復雜度和遍歷一樣，都是 O(n)。如果是二叉查找樹，則可以在 O(logn) 的時間復雜度內完成查找動作。樹結構在存在“一對多”的數據關系中，可被高頻使用，這也是它區別于鏈表系列數據結構的關鍵點。 #### 練習題 關于樹結構，我們留一道習題。給定一棵樹，按照層次順序遍歷并打印這棵樹。例如:  則打印 16、13、20、10、15、22、21、26。請注意，這并不是前序遍歷。 練習題代碼如下： ``` public static void levelTraverse(Node root) { if (root == null) { return; } LinkedList<Node> queue = new LinkedList<Node>(); Node current = null; queue.offer(root); // 根節點入隊 while (!queue.isEmpty()) { // 只要隊列中有元素，就可以一直執行，非常巧妙地利用了隊列的特性 current = queue.poll(); // 出隊隊頭元素 System.out.print("-->" + current.data); // 左子樹不為空，入隊 if (current.leftChild != null) queue.offer(current.leftChild); // 右子樹不為空，入隊 if (current.rightChild != null) queue.offer(current.rightChild); } } ```