C++樹 小結

重點回顧

• 二叉樹是一種非線性數(shù)據(jù)結構，體現(xiàn)“一分為二”的分治邏輯。每個二叉樹節(jié)點包含一個值以及兩個指針，分別指向其左子節(jié)點和右子節(jié)點。
• 對于二叉樹中的某個節(jié)點，其左（右）子節(jié)點及其以下形成的樹被稱為該節(jié)點的左（右）子樹。
• 二叉樹的相關術語包括根節(jié)點、葉節(jié)點、層、度、邊、高度和深度等。
• 二叉樹的初始化、節(jié)點插入和節(jié)點刪除操作與鏈表操作方法類似。
• 常見的二叉樹類型有完美二叉樹、完全二叉樹、滿二叉樹和平衡二叉樹。完美二叉樹是最理想的狀態(tài)，而鏈表是退化后的最差狀態(tài)。
• 二叉樹可以用數(shù)組表示，方法是將節(jié)點值和空位按層序遍歷順序排列，并根據(jù)父節(jié)點與子節(jié)點之間的索引映射關系來實現(xiàn)指針。
• 二叉樹的層序遍歷是一種廣度優(yōu)先搜索方法，它體現(xiàn)了“一圈一圈向外”的分層遍歷方式，通常通過隊列來實現(xiàn)。
• 前序、中序、后序遍歷皆屬于深度優(yōu)先搜索，它們體現(xiàn)了“走到盡頭，再回頭繼續(xù)”的回溯遍歷方式，通常使用遞歸來實現(xiàn)。
• 二叉搜索樹是一種高效的元素查找數(shù)據(jù)結構，其查找、插入和刪除操作的時間復雜度均為 O(log?n) 。當二叉搜索樹退化為鏈表時，各項時間復雜度會劣化至 O(n) 。
• AVL 樹，也稱為平衡二叉搜索樹，它通過旋轉(zhuǎn)操作，確保在不斷插入和刪除節(jié)點后，樹仍然保持平衡。
• AVL 樹的旋轉(zhuǎn)操作包括右旋、左旋、先右旋再左旋、先左旋再右旋。在插入或刪除節(jié)點后，AVL 樹會從底向頂執(zhí)行旋轉(zhuǎn)操作，使樹重新恢復平衡。

Q & A

對于只有一個節(jié)點的二叉樹，樹的高度和根節(jié)點的深度都是 0 嗎？

是的，因為高度和深度通常定義為“走過邊的數(shù)量”。

二叉樹中的插入與刪除一般都是由一套操作配合完成的，這里的“一套操作”指什么呢？可以理解為資源的子節(jié)點的資源釋放嗎？

拿二叉搜索樹來舉例，刪除節(jié)點操作要分為三種情況處理，其中每種情況都需要進行多個步驟的節(jié)點操作。

為什么 DFS 遍歷二叉樹有前、中、后三種順序，分別有什么用呢？

DFS 的前、中、后序遍歷和訪問數(shù)組的順序類似，是遍歷二叉樹的基本方法，利用這三種遍歷方法，我們可以得到一個特定順序的遍歷結果。例如在二叉搜索樹中，由于結點大小滿足 左子結點值 < 根結點值 < 右子結點值 ，因此我們只要按照 左->根->右 的優(yōu)先級遍歷樹，就可以獲得有序的節(jié)點序列。

右旋操作是處理失衡節(jié)點 node、child、grand_child 之間的關系，那 node 的父節(jié)點和 node 原來的連接不需要維護嗎？右旋操作后豈不是斷掉了？

我們需要從遞歸的視角來看這個問題。右旋操作 right_rotate(root) 傳入的是子樹的根節(jié)點，最終 return child 返回旋轉(zhuǎn)之后的子樹的根節(jié)點。子樹的根節(jié)點和其父節(jié)點的連接是在該函數(shù)返回后完成的，不屬于右旋操作的維護范圍。

在 C++ 中，函數(shù)被劃分到 private 和 public 中，這方面有什么考量嗎？為什么要將 height() 函數(shù)和 updateHeight() 函數(shù)分別放在 public 和 private 中呢？

主要看方法的使用范圍，如果方法只在類內(nèi)部使用，那么就設計為 private 。例如，用戶單獨調(diào)用 updateHeight() 是沒有意義的，它只是插入、刪除操作中的一步。而 height() 是訪問結點高度，類似于 vector.size() ，因此設置成 public 以便使用。

請問如何從一組輸入數(shù)據(jù)構建一個二叉搜索樹？根節(jié)點的選擇是不是很重要？

是的，構建樹的方法已在二叉搜索樹代碼中的 build_tree() 方法中給出。至于根節(jié)點的選擇，我們通常會將輸入數(shù)據(jù)排序，然后用中點元素作為根節(jié)點，再遞歸地構建左右子樹。這樣做可以最大程度保證樹的平衡性。

在 Java 中，字符串對比是否一定要用 equals() 方法？

在 Java 中，對于基本數(shù)據(jù)類型，== 用于對比兩個變量的值是否相等。對于引用類型，兩種符號的工作原理是不同的。

• == ：用來比較兩個變量是否指向同一個對象，即它們在內(nèi)存中的位置是否相同。
• equals()：用來對比兩個對象的值是否相等。

因此如果要對比值，我們通常會用 equals() 。然而，通過 String a = "hi"; String b = "hi"; 初始化的字符串都存儲在字符串常量池中，它們指向同一個對象，因此也可以用 a == b 來比較兩個字符串的內(nèi)容。

廣度優(yōu)先遍歷到最底層之前，隊列中的節(jié)點數(shù)量是 2? 嗎？

是的，例如高度 ?=2 的滿二叉樹，其節(jié)點總數(shù) ?=7 ，則底層節(jié)點數(shù)量 4=2?=(?+1)/2 。