---
tags: 資料結構, LeetCode
disqus: HackMD
---

# 樹(Tree)

:::spoiler 文章目錄
[toc]
:::

## 介紹

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

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


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

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

### 定義

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

## 真實應用

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

下圖為`DOM`樹範例

(圖片來自於[[資料結構] 樹 Tree](https://w3c.hexschool.com/blog/bc00a810))

## 建立樹的基本要點

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

## 實作基本的樹

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

[圖片使用syntree生成](https://mshang.ca/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）的實作，包含三個部分：

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

* `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)](https://iq.opengenus.org/dfs-vs-bfs/))

### 深度優先搜尋

深度優先搜尋詳細解說請參考[👉深度優先搜尋](https://hackmd.io/@SupportCoding/DFS)

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

1. 前序走訪 (Pre-Order Traversal)
2. 中序走訪 (In-Order Traversal)
3. 後序走訪 (Post-Order Traversal)

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

#### 前序走訪 (Pre-Order Traversal)

> 根節點排在前面

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


#### LeetCode實戰

[144. Binary Tree Preorder Traversal](https://leetcode.com/problems/binary-tree-preorder-traversal)

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

(圖片來自於[Wikimedia Commons](https://commons.wikimedia.org/wiki/Main_Page))

#### Code

[👉詳細說明](https://leetcode.com/problems/binary-tree-preorder-traversal/solutions/3033034/javascript-solutions-detail/?envType=study-plan&id=data-structure-i&orderBy=most_votes)

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

/**
 * 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](https://commons.wikimedia.org/wiki/Main_Page))

#### LeetCode實戰

[94. Binary Tree Inorder Traversal](https://leetcode.com/problems/binary-tree-inorder-traversal)

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


#### Code

[👉詳細說明](https://leetcode.com/problems/binary-tree-inorder-traversal/solutions/3038824/javascript-solutions-detail/?envType=study-plan&id=data-structure-i&orderBy=most_votes)

我們使用一個堆疊`(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](https://leetcode.com/problems/binary-tree-postorder-traversal)

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


#### Code

[👉詳細說明](https://leetcode.com/problems/binary-tree-postorder-traversal/solutions/3044353/javascript-simple-solution/?envType=study-plan&id=data-structure-i&orderBy=most_votes)

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

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

### 廣度優先搜尋

廣度優先搜尋詳細解說請參考[👉廣度優先搜尋](https://hackmd.io/@SupportCoding/BFS)

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

* 層序走訪

#### 層序走訪

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


#### LeetCode實戰

[102. Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/)

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


#### Code

[👉詳細說明](https://leetcode.com/problems/binary-tree-level-order-traversal/solutions/3062350/javascript-solutions-detail/?orderBy=most_votes)

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

## 特別感謝

感謝[Howard Gou](https://hackmd.io/@toto6038)大大訂正