重點(diǎn)回顧

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

Q & A

對(duì)于只有一個(gè)節(jié)點(diǎn)的二叉樹(shù)，樹(shù)的高度和根節(jié)點(diǎn)的深度都是 0 嗎？

是的，因?yàn)楦叨群蜕疃韧ǔ６x為“走過(guò)邊的數(shù)量”。

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

拿二叉搜索樹(shù)來(lái)舉例，刪除節(jié)點(diǎn)操作要分為三種情況處理，其中每種情況都需要進(jìn)行多個(gè)步驟的節(jié)點(diǎn)操作。

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

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

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

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

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

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

請(qǐng)問(wèn)如何從一組輸入數(shù)據(jù)構(gòu)建一個(gè)二叉搜索樹(shù)？根節(jié)點(diǎn)的選擇是不是很重要？

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

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

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

• == ：用來(lái)比較兩個(gè)變量是否指向同一個(gè)對(duì)象，即它們?cè)趦?nèi)存中的位置是否相同。
• equals()：用來(lái)對(duì)比兩個(gè)對(duì)象的值是否相等。

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

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

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