樹(Tree)

介紹

在計算機科學中，樹是一種用來組織和儲存資料的抽象資料結構。樹是由節點和連接它們的邊構成的，其中一個節點被稱為根節點，它沒有父節點。其它節點可以有一個或多個父節點和零個或多個子節點。

樹是一種分層資料結構，因為它的節點在不同的層級上。從根節點開始，可以透過沿著邊向下移動來造訪樹中的每個節點。每個節點可以有任意數量的子節點，但每個子節點只能有一個父節點。

在資料結構中，樹通常是二元搜尋樹，每個節點最多有兩個子節點，分別稱為左子節點和右子節點。二元搜尋樹是最常用的樹之一，因為它們易於實作且非常高效。二元搜尋樹可以用於實現搜尋樹、Heap、霍夫曼編碼（Huffman Coding）等資料結構。

(此為二元搜尋樹Binary Search tree)

定義

樹是一個沒有loop的Graph，所以下圖不是一個樹
樹必須有一個，也只能有一個根root

真實應用

文件系統中的文件夾
電子郵件信箱中的文件夾
HTML文檔中的DOM(Document Object Model)樹
自然語言處理

下圖為DOM樹範例

(圖片來自於[資料結構] 樹 Tree)

建立樹的基本要點

確定樹的根節點：樹的根節點是整棵樹的開始，通常是從根節點開始進行操作。如果樹是空的，則根節點可以是null。
定義節點的結構：確定樹的節點結構，包括每個節點的值和指向其子節點的指標。可以使用 struct 或 class 來定義節點的結構。
建立節點：使用節點結構定義，建立每個節點。可以透過分配記憶體（如 malloc()、new）或從 object pool 中獲取節點來建立節點。
建立連接關係：通過將父節點的指標指向其子節點，來建立樹中節點之間的連接關係。可以使用遞迴或迭代演算法來建立連接關係，具體取決於應用程式的需求。
走訪樹：走訪樹是指按照一定的順序造訪樹的所有節點。常見的走訪方式包括前序走訪、中序走訪和後序走訪，也可以使用層序走訪來造訪樹的所有節點。
處理樹的操作：對樹進行查找、插入、刪除等操作。可以使用遞迴或迭代演算法來實作這些操作，具體取決於應用程式的需求。

實作基本的樹

撰寫一個JS程式碼範例，該範例會產生樹，並且該樹的結構類似於下面提供的圖片。

圖片使用syntree生成

在這個範例中，我們建立了一個 TreeNode 類別，每個節點有一個 value 屬性代表該節點的值，以及一個 children 屬性代表該節點的子節點。

class TreeNode {
    constructor(value) {
        this.value = value;
        this.children = [];
    }

    addChild(node) {
        this.children.push(node);
    }
}

const root = new TreeNode(1);
const node2 = new TreeNode(2);
const node3 = new TreeNode(3);
const node4 = new TreeNode(4);
const node5 = new TreeNode(5);

root.addChild(node2);
root.addChild(node3);
node2.addChild(node4);
node2.addChild(node5);

console.log(root);

實作二元搜尋樹

以下程式碼是一個二分搜尋樹（Binary Search Tree, BST）的實作，包含三個部分：

TreeNode 類別：代表樹中的一個節點，包含一個值、一個左子節點和一個右子節點。
BinarySearchTree 類別：代表一個二分搜尋樹，包含一個根節點和一些操作方法，如插入、尋找和刪除節點。
操作方法：

insert(value)：插入一個值為 value 的節點到樹中，如果樹為空則新節點設為根節點。如果值已經存在於樹中，則返回 undefined。
下圖為範例所產生二元搜尋樹
find(value)：在樹中尋找值為 value 的節點，如果找到則返回該節點，否則返回 false。
remove(value)：從樹中刪除值為 value 的節點。如果值不存在於樹中，則返回 false。

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    insert(value) {
        const newNode = new TreeNode(value);
        if (this.root === null) {
            this.root = newNode;
            return this;
        } else {
            let current = this.root;
            while (true) {
                if (value === current.value) return undefined;
                if (value < current.value) {
                    if (current.left === null) {
                        current.left = newNode;
                        return this;
                    } else {
                        current = current.left;
                    }
                } else if (value > current.value) {
                    if (current.right === null) {
                        current.right = newNode;
                        return this;
                    } else {
                        current = current.right;
                    }
                }
            }
        }
    }

    find(value) {
        if (this.root === null) 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;
            }
        }
        if (!found) return false;
        return current;
    }

    remove(value) {
        if (this.root === null) return false;
        let current = this.root;
        let parent = null;
        let found = false;
        while (current && !found) {
            if (value < current.value) {
                parent = current;
                current = current.left;
            } else if (value > current.value) {
                parent = current;
                current = current.right;
            } else {
                found = true;
            }
        }
        if (!found) return false;
        if (current.left === null && current.right === null) {
            if (current.value < parent.value) {
                parent.left = null;
            } else if (current.value > parent.value) {
                parent.right = null;
            }
        } else if (current.left === null) {
            if (current.value < parent.value) {
                parent.left = current.right;
            } else if (current.value > parent.value) {
                parent.right = current.right;
            }
        } else if (current.right === null) {
            if (current.value < parent.value) {
                parent.left = current.left;
            } else if (current.value > parent.value) {
                parent.right = current.left;
            }
        } else {
            let temp = current.right;
            while (temp.left !== null) {
                temp = temp.left;
            }
            current.value = temp.value;
            if (temp.right === null) {
                temp = null;
            } else {
                temp.value = temp.right.value;
                temp.right = null;
            }
        }
    }
}

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(13);
bst.insert(11);
bst.insert(2);
bst.insert(16);
console.log(bst.find(11));
console.log(bst.remove(13));
console.log(bst);

樹的走訪Tree Traversal

樹的走訪大致分成下面兩項

深度優先搜尋(deppth-first search)簡稱DFS
廣度優先搜尋(breadth-first search)簡稱BFS

(圖片來自於DFS vs BFS (in detail))

深度優先搜尋

深度優先搜尋詳細解說請參考👉深度優先搜尋

樹的走訪在深度優先搜尋中為以下三種方式，分別代表根節點在走訪時的位置：

前序走訪 (Pre-Order Traversal)
中序走訪 (In-Order Traversal)
後序走訪 (Post-Order Traversal)

接下來再個別探討的過程中，皆以二元搜尋樹做為範例。

前序走訪 (Pre-Order Traversal)

根節點排在前面

前序走訪（Pre-Order Traversal）是依序以根節點、左節點、右節點為順序走訪的方式。

LeetCode實戰

144. Binary Tree Preorder Traversal

題目: 給定一個二元搜尋樹，傳回其前序走訪的值。

(圖片來自於Wikimedia Commons)

Code

👉詳細說明

前序走訪是根->左->右，我們先用一個陣列儲存要輸出的值，檢查節點是否為空，否的話則將值儲存至陣列，並利用遞迴的方式持續檢查左右子節點，最後再傳回該陣列即可。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    var target = []
    
    function dfs(node){
        if (!node){
            return;
        }
        target.push(node.val)
        dfs(node.left)
        dfs(node.right)
    }
    dfs(root)
    return target
};

中序走訪 (In-Order Traversal)

根節點排在中間

中序走訪（In-Order Traversal）是依序以左節點、根節點、右節點為順序走訪的方式。

(圖片來自於Wikimedia Commons)

LeetCode實戰

94. Binary Tree Inorder Traversal

題目: 給定一個二元搜尋樹，傳回其中序走訪的值。

Code

👉詳細說明

我們使用一個堆疊(stack)來存儲遍歷過的節點，並使用一個變量 curr 來記錄當前訪問的節點。

當 curr 為空時，從堆疊中彈出一個節點 curr，將其值存儲到 target 陣列中，然後將 curr 設置為其右子節點。因為在中序走訪中，左子節點必須先於根節點被處理，所以我們先處理完左子節點，再處理根節點，最後再處理右子節點。這樣保證了按照中序走訪的順序進行訪問。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let target = []
    let stack = []
    let curr = root
    while (curr != null || !stack.length == 0) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        target.push(curr.val);
        curr = curr.right;
    }
    return target;
};

後序走訪 (Post-Order Traversal)

根節點排在最後

後序走訪（Post-Order Traversal）是依序以左節點、右節點、根節點為順序走訪的方式。

題目: 給定一個二元搜尋樹，傳回其後序走訪的值。

LeetCode實戰

145. Binary Tree Postorder Traversal

題目: 給定一個二元搜尋樹，傳回其後序走訪的值。

Code

👉詳細說明

這邊解法有點像是把它反推回去，將節點往前加入陣列。

在 while 迴圈中，將 current 的值加入結果陣列 result 的開頭，此為後序遍歷的特點。
將 current 加入堆疊 stack 中。
將 current 更新為其右子節點，一路向右子樹走，直到無法再往右。
當 current 為空時，表示已經走到了右子樹的底部，此時從堆疊 stack 中彈出一個節點，將 current 更新為該節點的左子節點，以便繼續遍歷左子樹。因為左子樹已經遍歷完畢，所以這裡不需要將該節點加入結果陣列 result 中。
重複執行步驟 1-4，直到 current 為空且堆疊 stack 也為空，表示已經遍歷完整棵樹。

最後，回傳遍歷結果陣列 result。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    let result = [];
    let stack = [];
    let current = root;
    while(current || stack.length) {
        while(current) {
            result.unshift(current.val);
            stack.push(current);
            current = current.right;
        }
        current = stack.pop();
        current = current.left;
    }
    return result;
};

廣度優先搜尋

廣度優先搜尋詳細解說請參考👉廣度優先搜尋

樹的走訪在廣度優先搜尋中的方式：

層序走訪

層序走訪

層序走訪會先造訪離根節點最近的節點，並由左至右存取。

LeetCode實戰

102. Binary Tree Level Order Traversal

題目: 給定一個二元搜尋樹，傳回其層序走訪的值。

Code

👉詳細說明

判斷樹是否為空，如果是，返回一個空陣列。
宣告一個 queue 陣列，並將根節點存入 queue。
宣告一個 result 陣列。
開始進行 while 迴圈，當 queue 不為空時，進入迴圈。
在迴圈中，宣告一個 level 陣列，代表當前層級的節點。
計算當前層級節點的數量，使用 size 變數存儲。
使用 for 迴圈，從 queue 中取出 size 個節點進行處理，直到當前層級所有節點處理完成。
將當前節點的值存入 level 陣列中。
如果當前節點有左子節點，將其加入 queue 中。
如果當前節點有右子節點，將其加入 queue 中。
將 level 陣列存入 result 二維陣列中。
迴圈結束後，返回 result 陣列。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if (root === null) return [];
    let queue = [root];
    let result = [];
    while (queue.length > 0) {
        let level = [];
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            let node = queue.shift();
            level.push(node.val);
            if (node.left !== null) queue.push(node.left);
            if (node.right !== null) queue.push(node.right);
        }
        result.push(level);
    }
    return result;
};