Tree

Tree Traversal

• Preorder/Inorder/Postorder 是 DFS method.
  • 函數呼叫次數都是 2n+1，$T(n)=O(n)$。
• Level-order 是 BFS method.

Implem. Example:

void preorder(treePtr node) {
    if (node == null) return;
    else {
        visit(node);
        preorder(node->lchild);
        preorder(node->rchild);
    }
}

Rebuild Tree

有兩種序，就有機會還原出唯一一棵二元樹。

比方說，只知道 preorder 和 inorder ，求出原本的二元樹。運用 Divide and Conquer：

preorder，VLR 最左邊的元素就是 root

inorder，LVR 兩邊分別為左右子樹，中間是 root

利用 root 便可區分左子樹和右子樹。子樹也是樹，可以用相同手法繼續分割，最後便可求出整棵樹的架構。但是只有 preorder 和 postorder 的話，是做不出答案的。因為無法確定樹根的位置。

References

• source:演算法筆記