什么是二叉樹

二叉樹是一種樹形資料結構，由節點組成，每個節點最多有兩個子節點，分別稱為左子節點和右子節點，在二叉樹中，每個節點的左子節點小于該節點的值，在該節點的右側的子節點大于該節點的值，

二叉樹的特點是易于搜索、插入和洗掉操作，

1. 在搜索時，從根節點開始，如果被查找值等于當前節點的值，則搜索結束，
2. 如果當前節點的值大于被查找值，則繼續搜索左子節點；
3. 如果當前節點的值小于被查找值，則繼續搜索右子節點，
4. 插入和洗掉節點的操作也類似，

二叉樹可分為滿二叉樹、完全二叉樹、平衡二叉樹、二叉搜索樹等多種型別，不同型別的二叉樹有不同的特點和應用場景，

1. 滿二叉樹是每個節點都有兩個子節點的二叉樹
2. 完全二叉樹則是除了最后一層節點之外，每一層節點都是滿的，最后一層節點從左往右排列，
3. 平衡二叉樹是指左右子樹高度差不超過1的二叉樹，
4. 二叉搜索樹是按照特定規則構建的二叉樹，每個節點的左子節點小于該節點的值，在該節點的右側的子節點大于該節點的值，

二叉樹在計算機科學領域中有廣泛的應用，例如在搜索演算法、編譯器、資料庫、作業系統等領域，

二叉樹的高度，深度，寬度，平衡是什么

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 =https://www.cnblogs.com/yyyyfly1/archive/2023/06/10/= 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）構建二叉搜索樹：可以通過前序遍歷的順序依次插入節點來構建二叉搜索樹，

標籤：其他

上一篇：配置證書與https

下一篇：返回列表