數據結構專欄 ?(click)

---

初識二叉樹：從基礎概念到實踐應用🌳

一、樹型結構基礎

1.1 樹的基本概念

樹是一種非線性的數據結構，由n(n>0)個有限節點組成一個具有層次關系的集合。它看起來像一棵倒掛的樹，根朝上而葉朝下。

關鍵特點：

• 有且僅有一個根節點，沒有前驅節點
• 除根節點外，其余節點被分成M(M>0)個互不相交的子樹
• 樹是遞歸定義的

重要術語：

• 結點的度：一個結點含有子樹的個數
• 樹的度：樹中所有結點度的最大值
• 葉子結點：度為0的結點
• 雙親結點/父結點：含有子結點的結點
• 孩子結點/子結點：一個結點含有的子樹的根結點
• 根結點：沒有雙親結點的結點
• 結點的層次：從根開始定義，根為第1層
• 樹的高度/深度：樹中結點的最大層次

1.2 樹的表示方法

最常用的表示方法是孩子兄弟表示法：

class Node {int value;        // 樹中存儲的數據Node firstChild;  // 第一個孩子引用Node nextBrother; // 下一個兄弟引用
}

二、二叉樹詳解

2.1 二叉樹概念

二叉樹是結點的一個有限集合，該集合：

1. 或者為空
2. 或者由一個根節點加上兩棵分別稱為左子樹和右子樹的二叉樹組成

特點：

• 二叉樹不存在度大于2的結點
• 二叉樹的子樹有左右之分，次序不能顛倒，是有序樹
  

2.2 特殊二叉樹

1. 滿二叉樹：每層的結點數都達到最大值。層數為K，結點總數是2^K-1
2. 完全二叉樹：深度為K，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從0至n-1的結點一一對應
   

2.3 二叉樹的性質

1. 非空二叉樹的第i層最多有2^(i-1)個結點
2. 深度為K的二叉樹最大結點數是2^K-1
3. 對于任何二叉樹，n0(葉子結點) = n2(度為2的結點) + 1
4. 具有n個結點的完全二叉樹深度為?log?(n+1)?
5. 完全二叉樹的父子結點關系：
   • 父結點序號：(i-1)/2
   • 左孩子序號：2i+1
   • 右孩子序號：2i+2

2.4 二叉樹的存儲

鏈式存儲

// 孩子表示法
class Node {int val;    // 數據域Node left;  // 左孩子引用，常常代表左孩?為根的整棵左?樹 Node right; // 右孩子引用，常常代表右孩?為根的整棵右?樹 
}// 孩子雙親表示法
class Node {int val;Node left;  // 左孩子引用，常常代表左孩?為根的整棵左?樹 Node right; // 右孩子引用，常常代表右孩?為根的整棵右?樹 Node parent; // 當前節點的根節點
}

三、二叉樹遍歷

遍歷(Traversal)是指沿著某條搜索路線，依次對樹中每個結點均做?次且僅做?次訪問。訪問結點所做的操作依賴于具體的應?問題(比如：打印節點內容、節點內容加1)。遍歷是?叉樹上最重要的操作之一，是二叉樹上進行其它運算之基礎。

3.1 遞歸遍歷

1. (NLR)前序遍歷：根節點 -> 左子樹 -> 右子樹
2. (LNR)中序遍歷：左子樹 -> 根節點 -> 右子樹
3. (LRN)后序遍歷：左子樹 -> 右子樹 -> 根節點
   

// 前序遍歷
void preOrder(Node root) {if (root == null) return;System.out.print(root.val + " ");preOrder(root.left);preOrder(root.right);
}// 中序遍歷
void inOrder(Node root) {if (root == null) return;inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);
}// 后序遍歷
void postOrder(Node root) {if (root == null) return;postOrder(root.left);postOrder(root.right);System.out.print(root.val + " ");
}

3.2 層序遍歷

從根節點出發，按層次從上到下、從左到右訪問結點。

void levelOrder(Node root) {if (root == null) return;Queue<Node> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {Node cur = queue.poll();System.out.print(cur.val + " ");if (cur.left != null) queue.offer(cur.left);if (cur.right != null) queue.offer(cur.right);}
}

四、二叉樹基本操作

代碼示例：

// 獲取節點個數
int size(Node root) {if (root == null) return 0;return 1 + size(root.left) + size(root.right);
}// 獲取葉子節點個數
int getLeafNodeCount(Node root) {if (root == null) return 0;if (root.left == null && root.right == null) return 1;return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}// 獲取第k層節點個數
int getKLevelNodeCount(Node root, int k) {if (root == null || k <= 0) return 0;if (k == 1) return 1;return getKLevelNodeCount(root.left, k-1) + getKLevelNodeCount(root.right, k-1);
}// 獲取二叉樹高度
int getHeight(Node root) {if (root == null) return 0;return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}// 查找值為val的節點
Node find(Node root, int val) {if (root == null) return null;if (root.val == val) return root;Node left = find(root.left, val);if (left != null) return left;return find(root.right, val);
}

結語

二叉樹是數據結構中的核心內容，掌握好二叉樹對于理解更復雜的數據結構和算法至關重要。建議讀者在學習理論的同時，多動手實現代碼，解決實際問題，才能真正掌握二叉樹的精髓。

---