Data structure

資料結構：二元樹（二叉樹）的前序遍歷（Preorder Traversal）

前序遍歷（Preorder Traversal）

前序遍歷（Preorder traversal）是一種二叉樹遍歷的方式。

在前序遍歷中，首先訪問根節點，然後遞歸地遍歷左子樹，最後遞歸地遍歷右子樹。具體步驟如下：

  1. 訪問當前節點（根節點）。
  2. 遞歸地對當前節點的左子樹進行前序遍歷。
  3. 遞歸地對當前節點的右子樹進行前序遍歷。

下面是一個前序遍歷的示例，我們以二叉樹的形式展示：

     A
    / \
   B   C
  / \   \
 D   E   F

前序遍歷的結果是：A -> B -> D -> E -> C -> F

解釋過程：

  1. 首先訪問根節點 A。
  2. 然後遞歸地遍歷左子樹，訪問節點 B。
  3. 繼續遞歸地遍歷左子樹，訪問節點 D。
  4. 由於節點 D 是葉節點，沒有左子樹或右子樹，因此返回到節點 B。
  5. 繼續遍歷節點 B 的右子樹，訪問節點 E。
  6. 由於節點 E 是葉節點，沒有左子樹或右子樹，因此返回到節點 B。
  7. 返回到根節點 A，開始遍歷右子樹。
  8. 遍歷右子樹，訪問節點 C。
  9. 由於節點 C 的左子樹為空，直接遍歷右子樹，訪問節點 F。
  10. 由於節點 F 是葉節點，沒有左子樹或右子樹，遍歷完成。

因此，前序遍歷的結果是 A -> B -> D -> E -> C -> F。

實作

以下是以 JavaScript 實現前序遍歷（Preorder Traversal）的程式碼：

// 定義二元樹節點的結構
class TreeNode {
    constructor(val, left, right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// 前序遍歷函數
function preorderTraversal(root) {
    const result = [];
    traverse(root, result);
    return result;
}

// 輔助函數，用於遞歸遍歷節點
function traverse(node, result) {
    if (node === null) {
        return;
    }

    // 訪問當前節點的值
    result.push(node.val);

    // 遞歸遍歷左子樹
    traverse(node.left, result);

    // 遞歸遍歷右子樹
    traverse(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 preOrderTraversalResult = preorderTraversal(root);
console.log(preOrderTraversalResult); // 輸出：[4, 2, 1, 3, 6, 5, 7]

最後，如果你覺得我的分享對你有幫助，請給予我一個愛心，並且分享這篇文章，這將是對我最大的鼓勵！