二元樹是一種樹形資料結構，由節點組成，每個節點最多有兩個子節點，分別稱為左子節點和右子節點。在二元樹中，每個節點的左子節點小於該節點的值，在該節點的右側的子節點大於該節點的值。
二元樹的特點是易於搜尋、插入和刪除操作。
二元樹可分為滿二元樹、完全二元樹、平衡二元樹、二元搜尋樹等多種型別，不同型別的二元樹有不同的特點和應用場景。
二元樹在電腦科學領域中有廣泛的應用，例如在搜尋演演算法、編譯器、資料庫、作業系統等領域。
1. 二元樹的高度：
二元樹的高度是指從根節點到最深節點的距離，即根節點到最遠葉子節點的最短路徑。一般使用遞迴演演算法來計算二元樹的高度，即樹的高度等於左子樹高度和右子樹高度中的較大值加一。
例如，對於下圖所示的二元樹，其高度為4：
A
/ \
B C
/ \ \
D E F
\
G
2. 二元樹的深度：
二元樹的深度是指從根節點到某個節點的距離，即從根節點到該節點的路徑上經過的節點數。如果該節點是根節點，則深度為0，否則深度等於其父節點的深度加一。
例如，對於上圖中的節點B，其深度為1，節點G的深度為3。
3.二元樹的寬度：
二元樹的寬度指的是二元樹某一層中最多節點的個數。為了計算樹的寬度，需要使用BFS（廣度優先搜尋）演演算法，從根節點開始逐層遍歷二元樹，記錄每一層中節點的個數（即該層寬度），然後取所有層寬度的最大值即可。
例如，對於下面這棵二元樹：
A
/ \
B C
/ \ \
D E F
如果從根節點開始遍歷二元樹，每一層中節點的個數為：
* 第1層：1個節點
* 第2層：2個節點
* 第3層：3個節點
因此，這棵二元樹的寬度是3。
需要注意的是，如果二元樹的某一層節點數目很少，那麼這一層的寬度可能會影響樹的整體寬度。在實際應用中，通常會根據具體場景選擇不同的度量標準，如節點數、邊數、佔用的儲存空間等。
4. 平衡二元樹：
平衡二元樹是指一棵二元樹，其中任意節點的左右子樹的深度差不超過1。在平衡二元樹中，所有節點的左右子樹深度差別不大，能夠保證樹在查詢、插入和刪除操作時，均能保持較高的效能表現。
例如，下圖所示的二元樹就是一棵平衡二元樹：
A
/ \
B C
/ \ / \
D E F G
左右子樹的深度差不超過1，左子樹深度為2，右子樹深度為2，因此它是一棵平衡二元樹。
二元樹的節點數與高度的關係可以表示為：如果二元樹的高度為h，則節點總數為2^(h+1) - 1
葉子節點數與高度的關係可以表示為：如果二元樹的高度為h，則葉子節點總數最多為2^h，最少為2^(h-1)。
因此，葉子節點數的範圍是 [2^(h-1), 2^h]，並且二元樹的葉子節點數和節點總數之間的關係是近似線性的。
1. 概念
前序遍歷是二元樹遍歷的一種方法，也叫做先根遍歷。在前序遍歷中，首先存取根節點，然後依次遍歷其左子樹和右子樹。具體來說，在前序遍歷中，每個節點的存取順序為：根節點 → 左子樹 → 右子樹。
2. 步驟
前序遍歷的步驟如下：
(1) 存取二元樹的根節點。
(2) 遞迴遍歷左子樹，直到左子樹為空。
(3) 遞迴遍歷右子樹，直到右子樹為空。
3. 虛擬碼
前序遍歷的虛擬碼如下：
function preorderTraversal(root) {
if (root == null) {
return;
}
visit(root); // 存取根節點
preorderTraversal(root.left); // 遍歷左子樹
preorderTraversal(root.right); // 遍歷右子樹
}1. 概念
中序遍歷是二元樹遍歷的一種方法。在中序遍歷中，二元樹的節點按照以下順序依次遍歷：左子樹 → 根節點 → 右子樹。
2. 步驟
中序遍歷的步驟如下：
(1) 遞迴遍歷左子樹，直到左子樹為空。
(2) 存取二元樹的根節點。
(3) 遞迴遍歷右子樹，直到右子樹為空。
3. 虛擬碼
中序遍歷的虛擬碼如下：
function inorderTraversal(root) {
if (root == null) {
return;
}
inorderTraversal(root.left); // 遍歷左子樹
visit(root); // 存取根節點
inorderTraversal(root.right); // 遍歷右子樹
}1. 概念
後序遍歷是二元樹遍歷的一種方法。在後序遍歷中，二元樹的節點按照以下順序依次遍歷：左子樹 → 右子樹 → 根節點。
2. 步驟
後序遍歷的步驟如下：
(1) 遞迴遍歷左子樹，直到左子樹為空。
(2) 遞迴遍歷右子樹，直到右子樹為空。
(3) 存取二元樹的根節點。
3. 虛擬碼
後序遍歷的虛擬碼如下：
function postorderTraversal(root) {
if (root == null) {
return;
}
postorderTraversal(root.left); // 遍歷左子樹
postorderTraversal(root.right); // 遍歷右子樹
visit(root); // 存取根節點
}二元搜尋樹中查詢某個元素的步驟如下：
1. 從二元搜尋樹的根節點開始遍歷。
2. 如果當前節點為空，則返回null；如果當前節點的值等於目標值，則返回當前節點。
3. 如果當前節點的值大於目標值，則以當前節點的左子樹為目標繼續查詢；如果當前節點的值小於目標值，則以當前節點的右子樹為目標繼續查詢。
4. 重複執行第2和第3步，直到找到目標節點或者遍歷至葉子節點為止。
虛擬碼如下所示：
function search(root, target):
if (root == null) return null // 如果根節點為空，則直接返回null
if (root.value == target) return root // 如果根節點的值等於目標值，則返回根節點
if (root.value > target) // 如果根節點的值大於目標值，則在左子樹中查詢
return search(root.left, target)
else // 如果根節點的值小於目標值，則在右子樹中查詢
return search(root.right, target)二元搜尋樹中查詢某個元素的時間複雜度是O(log N)，其中N為二元搜尋樹中節點的數量。這是因為每次查詢都會將搜尋區域縮小一半，因此查詢的次數最多是二元樹深度的兩倍，而二元樹深度是log N級別的。
1. 概念
二元搜尋樹是一種特殊的二元樹，它滿足以下性質：對於每個節點，它的左子樹的所有節點的值小於該節點的值，它的右子樹的所有節點的值大於該節點的值。
插入操作是指向二元搜尋樹中新增新節點的過程，使得二元搜尋樹仍然保持其有序性。
2. 步驟
二元搜尋樹的插入操作步驟如下：
(1) 從根節點開始查詢，比較當前節點的值和待插入節點的值。
(2) 如果當前節點為空，則將待插入節點插入到該位置，完成插入操作。
(3) 如果待插入節點的值小於當前節點的值，則在左子樹中繼續查詢。
(4) 如果待插入節點的值大於當前節點的值，則在右子樹中繼續查詢。
(5) 對查詢到的節點重複上面的操作，直到找到合適的位置將待插入節點插入到樹中。
3. 虛擬碼
二元搜尋樹的插入操作的虛擬碼如下：
function insert(root, val) {
if (root == null) {
root = new TreeNode(val);
return root;
}
if (val < root.val) {
root.left = insert(root.left, val);
} else if (val > root.val) {
root.right = insert(root.right, val);
}
return root;
}1. 概念
二元搜尋樹的刪除操作是指從二元搜尋樹中刪除一個節點的過程，同時保證刪除後的二元搜尋樹仍然滿足其有序性質。
2. 步驟
二元搜尋樹的刪除操作步驟如下：
(1) 如果待刪除節點為葉子節點，則直接刪除該節點。
(2) 如果待刪除節點只有一個子節點，則將該子節點替換到待刪除節點的位置。
(3) 如果待刪除節點有兩個子節點，則先找到右子樹的最小值節點，使用該節點替換待刪除節點，並遞迴刪除右子樹中的最小值節點。
3. 虛擬碼
二元搜尋樹的刪除操作的虛擬碼如下：
function deleteNode(root, key) {
if (root === null) {
return null;
} else if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
if (root.left === null && root.right === null) {
root = null;
} else if (root.left === null) {
root = root.right;
} else if (root.right === null) {
root = root.left;
} else {
let minNode = findMin(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, minNode.val);
}
}
return root;
}
function findMin(node) {
while (node.left !== null) {
node = node.left;
}
return node;
}1. 二元樹的中序遍歷可以用來做什麼？
二元樹的中序遍歷方法是先存取左子樹，再存取根節點，最後存取右子樹；因此，中序遍歷可以幫助我們實現以下操作：
（1）從小到大遍歷二元搜尋樹：因為按照中序遍歷的順序，所有節點的值都會按從小到大的順序輸出，所以可以用中序遍歷將二元搜尋樹中的節點從小到大遍歷。
（2）建立二元搜尋樹：可以通過將節點按照中序遍歷的順序依次插入二元搜尋樹來建立一顆新的二元搜尋樹。
（3）查詢二元搜尋樹中的節點：通過進行中序遍歷，可以找到指定值的節點。
2. 二元樹的後序遍歷可以用來做什麼？
二元樹的後序遍歷方法是先存取左子樹，再存取右子樹，最後存取根節點；因此，後序遍歷可以幫助我們實現以下操作：
（1）計算二元樹表示式：可以通過後序遍歷以及棧的資料結構來計算二元樹表示式。
（2）釋放二元樹節點：通過後序遍歷的方式釋放二元樹的每一個節點。
（3）構建二元樹的映象：通過後序遍歷的方式，可以先構建出原二元樹的映象的右子樹，再構建出映象的左子樹，最後建立根節點，獲得二元樹的映象樹。
3. 二元樹的前序遍歷可以用來做什麼？
二元樹的前序遍歷方法是先存取根節點，再存取左子樹，最後存取右子樹；因此，前序遍歷可以幫助我們實現以下操作：
（1）序列化二元樹：可以按照前序遍歷的順序將二元樹轉換為字串，從而進行序列化操作。
（2）還原二元樹：通過前序遍歷和中序遍歷的結果，可以還原出原二元樹的結構。
（3）構建二元搜尋樹：可以通過前序遍歷的順序依次插入節點來構建二元搜尋樹。