Binary Tree: Traversal(尋訪)

Posted by Chiu CC on 12 24, 2015


先備知識與注意事項

在Linked list與Tree中的traversal中對於pointer的操作，在概念上完全相同，不過由於Node的pointer增加了，於是從一維的移動拓展到二維的移動。
建議讀者可以先閱讀Linked List: 新增資料、刪除資料、反轉作簡單複習。

本篇文章將介紹在Binary Tree中的四種traversal方法。

程式實作的部分，除了遞迴(recursion)，還有可能會使用上Stack(堆疊)與Queue(佇列)，如果不太熟悉，請參考：

目錄


Traversal in Binary Tree

Traversal(尋訪)有「站在A地，往所有與A地相連的地方移動」的意思：

  • 以Graph(圖)的語言來說，站在vertex(A)上，有一條edge連結vertex(A)與vertex(B)，若能夠由A往B移動，此即可視為traversal；
  • 在以pointer實現之Linked list和Tree中，站在node(A)上，並且node(A)具有指向node(B)之pointer，便能夠由A往B移動，此即可視為traversal。

移動到特定的node之後，通常伴隨著其他行為，例如print out(顯示資料)、assign(賦值)、刪除資料等等，這些操作又稱作Visiting。

Binary Tree的Node具有兩個指向child的pointer，traversal以「當前所在的node」為參考點，所能夠進行的行為有三種：

  • V：Visiting，對當前所在的node進行print、assign或其他操作。
  • L：移動到left child。
  • R：移動到right child。

VLR

圖一：CurrentNode位在A，leftchild與rightchild分別為B與C。

以圖一為例，假設現在CurrentNode位在A，leftchild與rightchild分別為B與C，並加上一項限制：「L一定在R之前」，便能產生三種相對關係：

VLR_pre

圖二(a)-(c) 依序為： (a)pre-order：VLR、(b)in-order：LVR、(c)post-order：LRV

pre-order(VLR)：當CurrentNode移動到A時，會先對A進行Visiting，接著前往left child進行Visiting，再前往right child進行Visiting。(若child指向NULL則忽略。)

in-order(LVR)：當CurrentNode移動到A時，會先對A的left child(B)進行Visiting，接著回到A進行Visiting，再前往right child(C)進行Visiting。(若child指向NULL則忽略。)

post-order(LRV)：當CurrentNode移動到A時，會先對A的left child(B)進行Visiting，再前往right child(C)進行Visiting，接著回到A進行Visiting。(若child指向NULL則忽略。)



小小備註：

  1. 以下圖例中，V表示CurrentNode所在的node，標上數字後表示已經Visiting完成，以print(顯示資料)為例，標上「\(1\)」表示該node第一個被印出。
  2. 以下文字說明，將使用scope(視野範圍)的概念，用來表示以每個CurrentNode(也就是V)為中心，與其所能夠指向之pointer所構成的範圍(等同於「迴圈」或者「函式呼叫」的scope)。因為每個迴圈都會改變CurrentNode(V)的位置，因此scope會以CurrentNode(V)為中心不停移動，直到迴圈/函式結束。

現有一棵樹如圖三(a)，欲進行post-order traversal，並將Visiting用作print(顯示資料)，流程如下：

bt_a

圖三(a)

一開始，CurrentNode進到A(root)，按照post-order的順序規則(LRV)，先檢查left child：B是否為NULL，若不是，則先將CurrentNode移動到B(L)：

bt_b

圖三(b)：scope內：A(V)、B(L)、C(R)。

當CurrentNode移動到B，再一次執行post-order的順序規則(LRV)，檢查left child：D是否為NULL，若不是，則將CurrentNode移動到D(L)：

bt_c

圖三(c)：scope內：B(V)、D(L)、E(R)。

當CurrentNode移動到D，再一次執行post-order的順序規則(LRV)，檢查出D的left child與right child皆為NULL，表示「LRV」的「L」與「R」都已經執行完畢，便「回到D」做Visiting，在此即印出D(print)。

接著，由於「以D為CurrentNode」形成的scope內之node已經全數Visiting完畢，便可回到「以D之parent作為CurrentNode之scope」，於是將CurrentNode移回B。

回到B的動作發生，即表示：以D為CurrentNode之迴圈或函式已經結束。

bt_d

圖三(d)：scope內：D(V)。

D已經進行過Visiting，便標上數字「\(1\)」，表示D為post-order traversal的第一站。
接著，在「以B為CurrentNode」的scope中，根據post-order規則，繼續往E(R)移動。

bt_e

圖三(e)：scope內：B(V)、D(L)、E(R)。

進入E後，因為E為leaf node，因此過程如圖三(d)，不會進入NULL。
在D(L)與E(R)都Visiting過後，便回到B(V)進行Visiting，並標上數字。如此便完成「以B為CurrentNode之scope」內的所有node之Visiting。

接著回到「以A為CurrentNode」的scope。

bt_f

圖三(f)：scope內：B(V)、D(L)、E(R)。

回到「以A為CurrentNode」的scope後，按照post-order的規則，接著往C(R)移動。

bt_g

圖三(g)：scope內：A(V)、B(L)、C(R)。

同樣地步驟，再從C移動至F(L)，並發現F為leaf node，於是對F進行Visiting，並標上數字。

bt_h

圖三(h)：scope內：C(V)、F(L)。

列出F後，發現C的right child指向NULL，於是略過right child(R)，回到C(V)，並對C進行Visiting，標上數字。

bt_ibt_j

圖三(i)-(j)：scope內：C(V)、F(L)。

最後回到「以A為CurrentNode」的scope，對A(V)進行Visiting，便完成了此次post-order traversal，並依序印出D E B F C A。

bt_kbt_l

圖三(k)-(l)：scope內：A(V)、B(L)、C(R)。

以上說明了post-order traversal之過程，另外兩種pre-order與in-order在概念上皆相同，只要把握順序規則即可。


Example with Code

(完整範例程式碼也可以看這裡：BT_Traversal.cpp)

接下來，再以一棵稍微複雜的Binary Tree作為範例，展示pre-order、in-order、post-order及level-order之traversal。

現有一棵樹如圖四(a)：

ex

圖四(a)：。

並以最暴力的方式建立TreeNode與BinaryTree之物件(object)：

// C++ code
#include <iostream>
#include <string>
#include <queue>

class BinaryTree;
class TreeNode{
public:
    TreeNode *leftchild;
    TreeNode *rightchild;
    TreeNode *parent;
    std::string str;

    TreeNode():leftchild(0),rightchild(0),parent(0),str(""){};
    TreeNode(std::string s):leftchild(0),rightchild(0),parent(0),str(s){};

    friend class BinaryTree;
};
class BinaryTree{
public:
    TreeNode *root;         // 以root作為存取整棵樹的起點
    BinaryTree():root(0){};
    BinaryTree(TreeNode *node):root(node){};

    void Preorder(TreeNode *current);
    void Inorder(TreeNode *current);
    void Postorder(TreeNode *current);
    void Levelorder();
};
// definition of BinaryTree::Preorder()
// definition of BinaryTree::Inorder()
// definition of BinaryTree::Postorder()
// definition of BinaryTree::Levelorder()
int main() {
    // TreeNode instantiation
    TreeNode *nodeA = new TreeNode("A"); TreeNode *nodeB = new TreeNode("B"); 
    TreeNode *nodeC = new TreeNode("C"); TreeNode *nodeD = new TreeNode("D"); 
    TreeNode *nodeE = new TreeNode("E"); TreeNode *nodeF = new TreeNode("F"); 
    TreeNode *nodeG = new TreeNode("G"); TreeNode *nodeH = new TreeNode("H"); 
    TreeNode *nodeI = new TreeNode("I");

    // construct the Binary Tree
    nodeA->leftchild = nodeB; nodeA->rightchild = nodeC; 
    nodeB->leftchild = nodeD; nodeB->rightchild = nodeE; 
    nodeE->leftchild = nodeG; nodeE->rightchild = nodeH; 
    nodeC->leftchild = nodeF; nodeF->rightchild = nodeI;

    BinaryTree T(nodeA);

    T.Preorder(T.root);
    std::cout << std::endl;
    T.Inorder(T.root);
    std::cout << std::endl;
    T.Postorder(T.root);
    std::cout << std::endl;
    T.Levelorder();
    std::cout << std::endl;    

    return 0;
}

上面的程式碼包含了幾個部分：

  • class TreeNode的定義；
    • 這裡把所有的data與pointer全部設成「public」裸露在外其實不太好，不過為了要能在main()裡土法煉鋼建立出一棵如圖四(a)的Binary Tree，只好將就。
    • 下一篇文章會用比較文明的方式建立Binary Tree，請參考：Binary Tree: 建立一棵Binary Tree。
  • class BinaryTree的定義，其中有四個member function分別為四種traversal；
    • 四個函式的定義請繼續看下去。
  • main()中建立如圖四(a)的樹，並依序執行四種traversal。

其中，pre-order、in-order、post-order traversal的邏輯就只是「V」、「L」、「R」誰先誰後的差別，以下程式碼是以較直覺的遞迴(recursion)形式完成，不過，換成迭代(iteration)配合Stack(堆疊)在概念上完全相同，實作上即是考慮「V」、「L」、「R」誰先push(推)進stack。

Pre-Order Traversal

// C++ code
void BinaryTree::Preorder(TreeNode *current){
    if (current) {                          // if current != NULL
        std::cout << current->str << " ";   // V
        Preorder(current->leftchild);       // L
        Preorder(current->rightchild);      // R
    }
}

output:

A B D E G H C F I

ex_pre

圖四(b)：。

In-Order Traversal

// C++ code
void BinaryTree::Inorder(TreeNode *current){
    if (current) {                          // if current != NULL
        Inorder(current->leftchild);        // L
        std::cout << current->str << " ";   // V
        Inorder(current->rightchild);       // R
    }
}

output:

D B G E H A F I C

ex_in

圖四(c)：。

Post-Order Traversal

// C++ code
void BinaryTree::Postorder(TreeNode *current){
    if (current) {                         // if current != NULL
        Postorder(current->leftchild);     // L
        Postorder(current->rightchild);    // R
        std::cout << current->str << " ";  // V
    }
}

output:

D G H E B I F C A

ex_post

圖四(d)：。

Level-Order Traversal

Level-order是照著「level由小到大」的順序，由上而下，並在同一個level「由左至右」依序Visiting每個node。

以下提供以迴圈配合Queue(佇列)實現level-order traversal之程式碼，其邏輯也非常直觀：

  • 以圖四(e)為例，當CurrentNode站在A時，先對A作Visiting，接著檢查是否有left child與right child，若不為NULL，則「依序」將child pointer 推(push)進queue中，又根據queue「先進先出」(first-in-first-out)的特性，先將B(left child)推入queue，再推入C(right child)，便能確保在下一層level時，是由左至右，先Visiting到B，才Visiting到C。

ex_level

圖四(e)：。

// C++ code
void BinaryTree::Levelorder(){

    std::queue<TreeNode*> q;
    q.push(this->root);                     // 把root作為level-order traversal之起點
                                            // 推進queue中
    while (!q.empty()){                     // 若queue不是空的, 表示還有node沒有visiting

        TreeNode *current = q.front();      // 取出先進入queue的node
        q.pop();                          
        std::cout << current->str << " ";   // 進行visiting

        if (current->leftchild != NULL){    // 若leftchild有資料, 將其推進queue
            q.push(current->leftchild);
        }
        if (current->rightchild != NULL){   // 若rightchild有資料, 將其推進queue
            q.push(current->rightchild);
        }
    }
}

output:

A B C D E F G H I


In-Order Traversal by Parent Field

在Binary Tree: Intro(簡介)提到，若在class TreeNode加入pointer指向其parent node會非常有幫助，其中一項理由正是接下來要介紹的兩個函式：InorderSuccessor()與InorderPredecessor()。

說文解字時間：

  • 字首Inorder-，即是按照inorder traversal之規則(LVR)；
  • 字尾Successor/ Predecessor，即是「下一個」與「前一個」。

因此，InorderSuccessor()與InorderPredecessor()便是用來尋找「以inorder順序」進行traversal之下一個與前一個node。

以圖四(c)為例，若CurrentNode站在H(CurrentNode = nodeH)，則：

  • CurrentNode = InorderSuccessor(CurrentNode)會將CurrentNode移動至A；
  • CurrentNode = InorderPredecessor(CurrentNode)則會將CurrentNode移動至E。

ex_in

圖四(c)：。

特別介紹inorder，一大原因是為了Binary Search Tree(BST)鋪路，在BST中，照著inorder順序印出node，就會得到「排好序」的資料。

另外，若觀察前面提過的遞迴(recursion)形式之inorder traversal，Visiting被包含在遞迴函式內，這表示若要進行多種不同的Visiting，例如print(顯示資料)、assign(賦值、更新資料)，都需要重新寫一個專門功能的遞迴函式。
顯然，把Visiting和Traversal獨立開來會更方便。

在看兩個實用的函式之前，有幾件前置作業：

  • 在class BinaryTree的定義中加入六個member function(成員函式)：
  • 在main()中，把如圖四之Binary Tree的parent pointer建立起來。
// C++ code
// inside main()

int main(){

    ...
    // link parent pointer
    nodeB->parent = nodeA; nodeC->parent = nodeA;
    nodeD->parent = nodeB; nodeE->parent = nodeB;
    nodeG->parent = nodeE; nodeH->parent = nodeE;
    nodeF->parent = nodeC; 
    nodeI->parent = nodeF;
    ...

}

// inside definition of class BinaryTree
class BinaryTree{
public:
    TreeNode *root;         // 以root作為存取整棵樹的起點
    BinaryTree():root(0){};
    BinaryTree(TreeNode *node):root(node){};

    void Preorder(TreeNode *current);
    void Inorder(TreeNode *current);
    void Postorder(TreeNode *current);
    void Levelorder();

    TreeNode* leftmost(TreeNode *current);
    TreeNode* rightmost(TreeNode *current);

    TreeNode* InorderSuccessor(TreeNode *current);
    TreeNode* InorderPredecessor(TreeNode *current);

    void Inorder_by_parent(TreeNode *root);
    void Inorder_Reverse(TreeNode *root);
};

其中包含：

  • InorderSuccessor()與InorderPredecessor()為找到「下一個」與「上一個」的函式主體；
  • leftmost()和rightmost()即是找到Binary Tree整棵樹中「最左」與「最右」的node；
  • Inorder_by_parent()與Inorder_Reverse()將利用InorderSuccessor()與InorderPredecessor()進行一次In-Order Tarversal。

看下去。

Successor、leftmost

函式leftmost()的功能為：尋找以current為root之subtree中，最左邊的node。

以圖四(c)為例，進入以A為root的Binary Tree後，leftmost()將一路往leftchild前進，最後回傳D。

  • 而以inorder的順序來說，leftmost()將回傳該subtree中第一個進行Visiting的node。

ex_in

圖四(c)：。

以下為leftmost()的範例程式碼：

// C++ code
TreeNode* BinaryTree::leftmost(TreeNode *current){
    while (current->leftchild != NULL){
        current = current->leftchild;
    }
    return current;
}



接著重點來了，觀察在inorder規則下，某一node的「Successor」之所在位置有兩種可能：

第一種：若CurrentNode的right child不是NULL，則CurrentNode之下一個順序的node即為以「Current\(-\)>rightchild為root」之subtree中，最左的node。

  • 如圖五(a)所示，若CurrentNode站在B上，B的下一個node即為「以B的right child(也就是E)為root」之subtree中的最左node，即為G。

第二種：若CurrentNode沒有right child，則CurrentNode之下一個順序的node是「以left child的身份尋找到的ancestor」。

  • 以圖五(a)中的H為例，H沒有right child，因此往上(往root方向)找ancestor。
  • 首先找到E，但是H是E的right child，因此再繼續往上找，此時CurrentNode移動到E。
  • 接著往E的parent找到B，由於E是B的right child，所以要再繼續往上找，並更新CurrentNode為B。
  • 接著往B的parent找到A，此時，B為A的left child，則A即為H的下一個順序的node。

特例是root，若整棵樹偏向一邊，root只有left subtree，沒有right subtree，那麼便回傳NULL，表示root沒有successor。

successor

圖五(a)：。

以下為InorderSuccessor()的範例程式碼：

// C++ code
TreeNode* BinaryTree::InorderSuccessor(TreeNode *current){
    if (current->rightchild != NULL){
        return leftmost(current->rightchild);
    }

    // 利用兩個pointer: successor與current做traversal 

    TreeNode *successor = current->parent;   
    while (successor != NULL && current == successor->rightchild) {
        current = successor;
        successor = successor->parent;
    }
    return successor;
}

最後，有了leftmost()與InorderSuccessor()，即能夠以迴圈的方式進行inorder traversal，相較於遞迴形式的函式，具有更大彈性，以函式Inorder_by_parent()呈現：

// C++ code
void BinaryTree::Inorder_by_parent(TreeNode *root){
    TreeNode *current = new TreeNode;
    current = leftmost(root);

    while(current){
        std::cout << current->str << " ";
        current = InorderSuccessor(current);
    }
}

在main()中輸入：

int main(){

    ...

    T.Inorder_by_parent(T.root);

    return 0;
}

得到output：

D B G E H A F I C



Predecessor、rightmost

只要把InorderSuccessor()與leftmost()中，所有的left與right互換，就得到InorderPredecessor()與rightmost()，而概念上也確實是如此：

rightmost：從「以CurrentNode為subtree」的root一路向右做Linked list的單向traversal。

Predecessor：某一CurrentNode的「前一個順序的node」之位置有兩種可能：

第一種：若CurrentNode的left child不是NULL，則CurrentNode之前一個順序的node即為以「Current->lefttchild為root」之subtree中，最右的node。

  • 如圖五(b)所示，若CurrentNode站在C上，C的前一個node即為「以C的left child(也就是F)」為root之subtree中的最右node，即為I。

第二種：若CurrentNode沒有left child，則CurrentNode之前一個順序的node是「以right child的身份尋找到的ancestor」。

  • 以圖五(b)中的F為例，F沒有left child，因此往上(往root方向)找ancestor。
  • 首先找到C，但是F是C的left child，因此再繼續往上找，此時CurrentNode更新成C。
  • 再往C的parent找到A，此時，C為A的right child，則A即為F的前一個順序的node。

同樣地，若整棵樹偏向一邊，root只有right subtree，沒有left subtree，則回傳NULL，表示root沒有predecessor。

predecessor

圖五(b)：。

以下為rightmost()與InorderPredecessor()的範例程式碼：

// C++ code
TreeNode* BinaryTree::rightmost(TreeNode *current){
    while (current->rightchild != NULL){
        current = current->rightchild;
    }
    return current;
}
TreeNode* BinaryTree::InorderPredecessor(TreeNode *current){
    if (current->leftchild != NULL){
        return rightmost(current->leftchild);
    }
    // 利用兩個pointer: predecessor與current做traversal
    TreeNode *predecessor = current->parent;

    while (predecessor != NULL && current == predecessor->leftchild) {
        current = predecessor;
        predecessor = predecessor->parent;
    }

    return predecessor;
}

有了rightmost()與InorderPredecessor()，便能夠照inorder traversal的相反順序對樹的node做Visiting，以函式Inorder_Reverse呈現：

// C++ code
void BinaryTree::Inorder_Reverse(TreeNode *root){
    TreeNode *current = new TreeNode;
    current = rightmost(root);

    while(current){
        std::cout << current->str << " ";
        current = InorderPredecessor(current);
    }
}

在main()中輸入：

int main(){

    ...

    T.Inorder_Reverse(T.root);

    return 0;
}

得到output：

C I F A H E G B D



InorderSuccessor()和InorderPredecessor()在Binary Search Tree的部分會再次出現，並且出現在基本操作：deletion(刪除node)中，因此學起來不止酷，還很實用的啊。


參考資料：


Binary Tree系列文章

Binary Tree: Intro(簡介)
Binary Tree: Traversal(尋訪)
Binary Tree: 建立一棵Binary Tree

回到目錄：

目錄：演算法與資料結構


tags: C++, Binary Tree,