樹結構的基本概念
樹是一種非線性數據結構，由節點和連接節點的邊組成。與線性數據結構（如數組、鏈表）不同，樹具有層次結構，非常適合表示有層次關系的數據。
樹的基本術語
- 節點 (Node)： 樹中的基本單元，包含數據和指向其他節點的引用
- 根節點 (Root)： 樹的頂部節點，沒有父節點
- 子節點 (Child)： 一個節點的直接下級節點
- 父節點 (Parent)： 一個節點的直接上級節點
- 葉節點 (Leaf)： 沒有子節點的節點
- 路徑 (Path)： 連接一個節點到另一個節點的節點序列
- 高度 (Height)： 從葉節點到該節點的最長路徑上的節點數
- 深度 (Depth)： 從根節點到該節點的邊數
JavaScript 實現基本樹結構
下面是一個使用 JavaScript 實現的基本樹結構：
class TreeNode {constructor(value) {this.value = value;this.children = [];}// 添加子節點addChild(childNode) {this.children.push(childNode);return this;}// 移除子節點removeChild(childNode) {const index = this.children.indexOf(childNode);if (index !== -1) {this.children.splice(index, 1);}return this;}// 深度優先遍歷depthFirstTraversal() {const result = []; function traverse(node) {result.push(node.value);node.children.forEach(child => traverse(child));} traverse(this);return result;}// 廣度優先遍歷breadthFirstTraversal() {const result = [];const queue = [this];while (queue.length > 0) {const currentNode = queue.shift();result.push(currentNode.value);currentNode.children.forEach(child => queue.push(child));} return result;}
}// 使用示例
const root = new TreeNode(1);
const child1 = new TreeNode(2);
const child2 = new TreeNode(3);
const grandChild1 = new TreeNode(4);
const grandChild2 = new TreeNode(5);child1.addChild(grandChild1);
child2.addChild(grandChild2);
root.addChild(child1).addChild(child2);console.log("深度優先遍歷:", root.depthFirstTraversal()); // [1, 2, 4, 3, 5]
console.log("廣度優先遍歷:", root.breadthFirstTraversal()); // [1, 2, 3, 4, 5]樹的常見類型
-
二叉樹 (Binary Tree)
二叉樹是一種特殊的樹，每個節點最多有兩個子節點，通常稱為左子節點和右子節點。class BinaryTreeNode {constructor(value) {this.value = value;this.left = null;this.right = null;} }class BinaryTree {constructor() {this.root = null;} // 插入節點insert(value) {const newNode = new BinaryTreeNode(value); if (!this.root) {this.root = newNode;return this;} let current = this.root;while (true) {if (value === current.value) return undefined; if (value < current.value) {if (!current.left) {current.left = newNode;return this;}current = current.left;} else {if (!current.right) {current.right = newNode;return this;}current = current.right;}}}// 查找節點find(value) {if (!this.root) return false; let current = this.root;let found = false; while (current && !found) {if (value < current.value) {current = current.left;} else if (value > current.value) {current = current.right;} else {found = true;}} return found ? current : false;}// 前序遍歷 (根 -> 左 -> 右)preOrderTraversal() {const result = []; function traverse(node) {result.push(node.value);if (node.left) traverse(node.left);if (node.right) traverse(node.right);} traverse(this.root);return result;} // 中序遍歷 (左 -> 根 -> 右)inOrderTraversal() {const result = []; function traverse(node) {if (node.left) traverse(node.left);result.push(node.value);if (node.right) traverse(node.right);} traverse(this.root);return result;} // 后序遍歷 (左 -> 右 -> 根)postOrderTraversal() {const result = []; function traverse(node) {if (node.left) traverse(node.left);if (node.right) traverse(node.right);result.push(node.value);} traverse(this.root);return result;} } // 使用示例 const binaryTree = new BinaryTree(); binaryTree.insert(10); binaryTree.insert(6); binaryTree.insert(15); binaryTree.insert(3); binaryTree.insert(8); binaryTree.insert(20); console.log("前序遍歷:", binaryTree.preOrderTraversal()); // [10, 6, 3, 8, 15, 20] console.log("中序遍歷:", binaryTree.inOrderTraversal()); // [3, 6, 8, 10, 15, 20] console.log("后序遍歷:", binaryTree.postOrderTraversal()); // [3, 8, 6, 20, 15, 10]
二叉搜索樹 (Binary Search Tree, BST)
二叉搜索樹是一種特殊的二叉樹，對于樹中的每個節點：
-
左子樹中所有節點的值都小于該節點的值
-
右子樹中所有節點的值都大于該節點的值
-
左右子樹也分別是二叉搜索樹
上面的二叉樹實現實際上就是一個二叉搜索樹的實現，它提供了高效的查找、插入和刪除操作，時間復雜度為 O (log n)。
平衡二叉樹 (AVL Tree)
平衡二叉樹是一種特殊的二叉搜索樹，它的每個節點的左右子樹的高度差不超過 1。這種平衡特性保證了樹的高度始終保持在 O (log n)，從而保證了所有操作的時間復雜度都是 O (log n)。
紅黑樹 (Red-Black Tree)
紅黑樹是一種自平衡的二叉搜索樹，它通過為每個節點分配一個顏色（紅色或黑色）并遵循一些特定的規則來保持樹的平衡。紅黑樹的平衡性不如 AVL 樹嚴格，但它的插入和刪除操作更快。
樹的遍歷方法
樹的遍歷是指按照某種順序訪問樹中的所有節點。主要有兩種遍歷方式：
-
深度優先遍歷 (DFS)
深度優先遍歷沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支。主要有三種實現方式：- 前序遍歷 (Pre-order)： 根節點 -> 左子樹 -> 右子樹
- 中序遍歷 (In-order)： 左子樹 -> 根節點 -> 右子樹
- 后序遍歷 (Post-order)： 左子樹 -> 右子樹 -> 根節點
-
廣度優先遍歷 (BFS)
廣度優先遍歷按照層次依次訪問樹中的節點，從上到下，從左到右。
樹結構的應用
樹結構在計算機科學和現實生活中有廣泛的應用：
- 文件系統： 文件和文件夾的層次結構
- 數據庫索引： B 樹和 B + 樹用于提高數據庫查詢效率
- 搜索引擎： 網頁的層次結構和索引
- XML 和 JSON 解析： 解析和處理層次化的數據
- 編譯器： 語法樹的構建和分析
- 游戲 AI： 決策樹和博弈樹
- 網絡路由算法： 最短路徑樹
樹是一種非常重要且靈活的數據結構，掌握樹的概念和實現對于理解和解決許多計算機科學問題至關重要。
