樹
樹的前中后序遍歷
樹是一種重要的非線性數據結構，尤其是二叉樹。二叉樹的遍歷是操作樹的基礎，主要有前序遍歷、中序遍歷和后序遍歷三種方式。
前序遍歷
訪問順序：根結點 -> 左子樹 -> 右子樹。
遍歷規則：首先訪問根結點，然后遞歸地遍歷左子樹，最后遞歸地遍歷右子樹。
代碼示例：
function preOrderTraversal(node) {if (!node) return;console.log(node.val);preOrderTraversal(node.left);preOrderTraversal(node.right);
}
中序遍歷：
訪問順序：左子樹 -> 根結點 -> 右子樹。
遍歷規則：首先遞歸地遍歷左子樹，然后訪問根結點，最后遞歸地遍歷右子樹。
代碼示例：
function inOrderTraversal(node) {if (!node) return;inOrderTraversal(node.left);console.log(node.val);inOrderTraversal(node.right);
}
后序遍歷：
訪問順序：左子樹 -> 右子樹 -> 根結點。
遍歷規則：首先遞歸地遍歷左子樹，然后遞歸地遍歷右子樹，最后訪問根結點。
代碼示例：
function postOrderTraversal(node) {if (!node) return;postOrderTraversal(node.left);postOrderTraversal(node.right);console.log(node.val);
}
樹排序算法
樹排序算法是一種基于二叉搜索樹的排序算法。樹排序通過將數據插入到二叉搜索樹中，然后進行中序遍歷從而實現排序。
二叉搜索樹的節點定義：
class TreeNode {constructor(val) {this.val = val;this.left = null;this.right = null;}
}
二叉搜索樹的性質：
對于樹中的每個節點，其左子樹中的所有節點值小于該節點值，右子樹中的所有節點值大于該節點值。
樹排序的實現：
構建二叉搜索樹：將待排序數據依次插入到二叉搜索樹中。
插入節點到二叉搜索樹：
function insert(root, val) {if (!root) return new TreeNode(val);if (val < root.val) {root.left = insert(root.left, val);} else {root.right = insert(root.right, val);}return root;
}
中序遍歷：對二叉搜索樹進行中序遍歷，得到一個有序序列。
代碼示例：
function inOrderTraversalCollect(root, sortedArray) {if (!root) return;inOrderTraversalCollect(root.left, sortedArray);sortedArray.push(root.val);inOrderTraversalCollect(root.right, sortedArray);
}
樹排序：
function treeSort(arr) {let root = null;for (let val of arr) {root = insert(root, val);}let sortedArray = [];inOrderTraversalCollect(root, sortedArray);for (let i = 0; i < arr.length; i++) {arr[i] = sortedArray[i];}
}// 測試樹排序
let arr = [5, 3, 8, 1, 2, 9];
console.log("排序前:");
console.log(arr);
treeSort(arr);
console.log("排序后:");
console.log(arr);
復雜度分析：
平均時間復雜度：O(n log n)，其中 n 是待排序的元素個數。
最壞時間復雜度：O(n^2)，當數據已經有序時，二叉搜索樹會退化為鏈表結構。
優化方法：使用平衡二叉搜索樹（如 AVL 樹或紅黑樹）代替普通二叉搜索樹，確保樹的高度保持在 O(log n)，從而保證時間復雜度為 O(n log n)。
總結
樹的前中后序遍歷是操作二叉樹的基礎，通過遞歸實現可以方便地訪問樹中的節點。樹排序算法是一種基于二叉搜索樹的排序算>法，通過中序遍歷可以得到有序序列。雖然樹排序的時間復雜度在平均情況下為 O(n log n)，但在最壞情況下會退化為 O(n^2)。>使用平衡二叉搜索樹可以有效地優化樹排序算法的性能。
