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):。

並以最暴力的方式建立TreeNodeBinaryTree之物件(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,