中序遍歷
中序遍歷（In-order traversal）是一種遍歷二叉樹的方法，其順序為先遍歷左子樹，然後訪問根節點，最後遍歷右子樹。
下面是中序遍歷的詳細過程：
- 如果當前節點為空，則返回。
- 對當前節點的左子樹進行中序遍歷，即遞歸調用中序遍歷函數，傳入當前節點的左子節點。
- 訪問當前節點，可以進行一些操作，例如將節點的值添加到結果列表中。
- 對當前節點的右子樹進行中序遍歷，即遞歸調用中序遍歷函數，傳入當前節點的右子節點。
以下是一個示例來說明中序遍歷的過程。假設我們有以下的二叉樹：
4
/ \
2 6
/ \ / \
1 3 5 7
按照中序遍歷的順序，我們應該依次訪問節點的值為 1, 2, 3, 4, 5, 6, 7。具體步驟如下：
- 從根節點開始遍歷，當前節點為 4。遞歸調用中序遍歷函數，傳入左子節點 2。
- 當前節點為 2，遞歸調用中序遍歷函數，傳入左子節點 1。
- 當前節點為 1，沒有左子節點，返回到節點 2。將節點 1 的值添加到結果列表中。
- 返回到節點 4，將節點 2 的值添加到結果列表中。遞歸調用中序遍歷函數，傳入右子節點 3。
- 當前節點為 3，沒有左子節點，返回到節點 4。將節點 3 的值添加到結果列表中。
- 返回到節點 4，將節點 4 的值添加到結果列表中。遞歸調用中序遍歷函數，傳入右子節點 6。
- 當前節點為 6，遞歸調用中序遍歷函數，傳入左子節點 5。
- 當前節點為 5，沒有左子節點，返回到節點 6。將節點 5 的值添加到結果列表中。
- 返回到節點 6，將節點 6 的值添加到結果列表中。遞歸調用中序遍歷函數，傳入右子節點 7。
- 當前節點為 7，沒有左子節點，返回到節點 6。將節點 7 的值添加到結果列表中。
- 返回到節點 6，返回到節點 4。
- 返回到根節點 4，遍歷完成。
範例程式碼
以下是一個使用 JavaScript 實現二叉樹中序遍歷的程式碼範例：
// 定義二叉樹的節點
class TreeNode {
constructor(val, left, right) {
this.val = val;
this.left = left;
this.right = right;
}
}
// 中序遍歷函數
function inorderTraversal(root) {
const result = []; // 用於儲存結果的陣列
inorder(root, result); // 呼叫中序遍歷輔助函數
return result;
}
// 中序遍歷輔助函數
function inorder(node, result) {
if (node === null) {
return;
}
// 遞歸遍歷左子樹
inorder(node.left, result);
// 將目前節點的值添加到結果陣列中，因為已經沒有比它更小的值了。目前節點的值就是最小的值。
result.push(node.val);
// 遞歸遍歷右子樹
inorder(node.right, result);
}
// 創建二叉樹
/**
* 4
* / \
* 2 6
* / \ / \
* 1 3 5 7
* / \ / \/ \ / \
* n n n nn n n n
*/
const root = new TreeNode(
4,
new TreeNode(2, new TreeNode(1, null, null), new TreeNode(3, null, null)),
new TreeNode(6, new TreeNode(5, null, null), new TreeNode(7, null, null))
);
// 執行中序遍歷
const inOrderTraversalResult = inorderTraversal(root);
console.log(inOrderTraversalResult); // 輸出 [1, 2, 3, 4, 5, 6, 7]
上述程式碼定義了一個 TreeNode 類別來表示二叉樹的節點，並使用遞歸的方式實現了中序遍歷的函數 inorderTraversal 和輔助函數 inorder。
在主程式中，我們創建了一個二叉樹，並執行中序遍歷，最後將結果輸出到控制台。
請注意，以上範例只是一個示例程式碼，可以根據自己的需求進行修改和擴展。
參考資料 👐
最後，如果你覺得我的分享對你有幫助，請給予我一個愛心，並且分享這篇文章，這將是對我最大的鼓勵！