樹的遍歷

重建樹

根據給定原始樹的先序遍歷 (preorder traversal) 和中序遍歷 (inorder traversal)重構原始樹。

前序遍歷的順序為 [根結點、左子樹、右子樹]，而中序遍歷的順序為 [左子樹、根結點、右子樹]，因此我們可以透過前序遍歷的第一個元素找到根結點，將其帶入中序遍歷，就可以找到左、右子樹，對左、右子樹遞迴進行此行為就可以構造出原始樹，
函式程式碼：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
TreeNode* BuildTree(string preord, string inord, int preord_left, int preord_right, int inord_left, int inord_right) {
    if (preord_left > preord_right) {
        return NULL;
    }
    //從前序遍歷中取得根結點
    int preord_root = preord_left;
    //找到根結點在中序遍歷中的位置
    int inord_root = inord.find(preord[preord_root]); 

    //構造根結點
    TreeNode* root = new TreeNode(preord[preord_root]);
    int size_left_subtree = inord_root - inord_left;
    //構造左子樹
    root->leftChild = BuildTree(preord, inord, preord_left + 1, preord_left + size_left_subtree, inord_left, inord_root - 1);
    //構造右子樹
    root->rightChild = BuildTree(preord, inord, preord_left + size_left_subtree + 1, preord_right, inord_root + 1, inord_right);
    return root;
}

二元搜尋樹

給定一棵二元搜尋樹 (binary search tree) 的先序遍歷 (preorder traversal)，重構出原始樹。

二元搜尋樹的特性：

  • 一個節點的左子樹只包含鍵值小於該節點的節點。
  • 一個節點的右子樹只包含鍵值大於該節點的節點。
  • 左子樹和右子樹也都是二分搜尋樹。

因為有以上特性，在區分左、右子樹時不需要利用到原始樹的中序遍歷，只要在前序遍歷中找到鍵值大於根結點的地方就是右子樹了，之後也是利用遞迴的方式建構出原始樹。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
TreeNode* BuildTree(int preord[], int left, int right) {
    if (left > right) {
        return NULL;
    }
    //從前序遍歷中取得根結點
    int preord_root = left;
    int size_left_subtree = 0;
    //找到右子樹在前序遍歷中的位置
    for(int i = left+1; i <= right; i++){
        if(preord[i] > preord[preord_root]) break;
        size_left_subtree++;
    }

    //構造根結點
    TreeNode* root = new TreeNode(preord[preord_root]);
    //構造左子樹
    root->leftChild = BuildTree(preord, left + 1, left + size_left_subtree);
    //構造右子樹
    root->rightChild = BuildTree(preord, left + size_left_subtree + 1, right);
    return root;
}

最小生成樹

Prim’s algorithm

  1. 設定初始節點，將其加入最小生成樹中。
  2. 在包含已選中與未選中的邊 (一端選中一端未選中) 中尋找權重最小者，將其加入最小生成樹中。
  3. 重複步驟 2 直到所有點都在最小生成樹內。

Kruskal’s algorithm

  1. 將所有邊依照權重由小排到大。
  2. 選擇權重最小邊，加入最小生成樹中。
  3. 檢查最小生成樹是否形成 circle，如果有則刪除剛剛加入的邊。
  4. 重複步驟 2 3 直到所有邊都考慮完畢。

Sollin’s algorithm

  1. 把每個點都當成一棵樹。
  2. 在所有樹中挑選出權重最小的邊。
  3. 如果有重複的邊只要保留一個，並且將選中的邊加入最小生成樹。
  4. 重複步驟 2 3 直到只剩下一顆樹 or 所有邊都已考慮完畢。