close

其實關於這個東西呢，網路上已經有各種資料跟code可以看了

比如說這個：https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/

我只是想紀錄一下，讓自己比較有印象而已XD

 

大概可以分成inorder、preorder、postorder和levelorder四種

前面三種又是俗稱的depth-first search(深度優先搜尋)，只是輸出的順序不一樣

levelorder又可以叫做breath-first search(好像叫廣度優先搜尋)

有什麼區別呢，接下來就來看看

1. inorder：

會依照左邊，root，右邊的順序去尋訪

code的話比較常見是用遞迴的方式去做，假設我要印出節點裡的值：

void inorder(TreeNode* root)

{

    if (root == nullptr) return;

    inorder(root->left);

    cout << root->val;

    inorder(root->right);

}

除了用遞迴之外，也可以用stack的方式來做

就是把root先存到stack裡面， 然後利用stack先進後出的特性來做

void inorder(TreeNode* root)

{

    stack<TreeNode*> s;

    TreeNode* cur = root;

    while (cur != nullptr || !s.empty()) 

    {

        while (cur->left)

        {

             s.push(cur);

             cur = cur->left;

        }

        // 跳出上面那個迴圈，表示已經沒有左子樹了

        cur = s.top();  // 此時stack中最上面的節點就會是最左邊子樹的節點

        cout << cur->val;

        s.pop();

        cur = cur->right;  // 如果有右子樹的話，就要從現在節點的右子樹開始尋訪

    }

}

對於BST(binary search tree)來說，如果用inorder的方式尋訪，就會印出排好序的數列

貌似很多題目都會用到這個特性

 

2. preorder：

就是root -> left -> right

常見的也是用遞迴來做

code大概長成這樣：

void preorder(TreeNode* root)

{

    if (root == nullptr) return;

    cout << root->val;

    preorder(root->left);

    preorder(root->right);

}

有發現嗎，其實只是換個順序而已

所以對於tree的traversal這個問題來說，遞迴的概念就很重要了

比需要對遞迴有一定的熟悉，才能夠應用到不同的情況

 

3. postorder

和上面差不多，換個順序而已

void postorder(TreeNode* root)

{

    if (root == nullptr) return;

    postorder(root->left);

    postorder(root->right);

    cout << root->val;

}

應該不會很難懂吧，主要還是熟悉度的問題

再來這一個比較不一樣

 

4. levelorder

意思就是從level最小的開始尋訪，從最上層開始往下找這樣

這個可以用遞迴或是用queue來做

個人覺得用queue的方式比較好做，就先看怎麼用queue的方式做吧：

註：這段是來自https://www.geeksforgeeks.org/level-order-tree-traversal/的，因為這排版實在很難打字...

void printLevelOrder(Node *root)
{
    // Base Case
    if (root == NULL)  return;
  
    // Create an empty queue for level order tarversal
    queue<Node *> q;
  
    // Enqueue Root and initialize height
    q.push(root);
  
    while (q.empty() == false)
    {
        // Print front of queue and remove it from queue
        Node *node = q.front();
        cout << node->data << " ";
        q.pop();
  
        /* Enqueue left child */
        if (node->left != NULL)
            q.push(node->left);
  
        /*Enqueue right child */
        if (node->right != NULL)
            q.push(node->right);
    }
}

雖說上面這樣可以把所有值依照順序印出來，不過如果要算level之類的東西的話，我會稍微加一點東西：

void printLevelOrder(Node *root)
{
    // Base Case
    if (root == NULL)  return;
  
    // Create an empty queue for level order tarversal
    queue<Node *> q;
  
    // Enqueue Root and initialize height
    q.push(root);
  
  while (q.empty() == false)
{
  int size = q.size();
for (int i = 0; i < size; ++i)
     {
         // Print front of queue and remove it from queue
         Node *node = q.front();
         cout << node->data << " ";
         q.pop();
  
         /* Enqueue left child */
         if (node->left != NULL)
             q.push(node->left);
  
         /*Enqueue right child */
         if (node->right != NULL)
             q.push(node->right);
     }
}
}

這樣等於是一層一層的尋訪，個人覺得比較有feel

 

遞迴的話要先知道總共有幾個level，所以要有一些輔助的function：

這些code也是來自https://www.geeksforgeeks.org/level-order-tree-traversal/的

void printLevelOrder(node* root) 
{ 
    int h = height(root); 
    int i; 
    for (i = 1; i <= h; i++) 
        printGivenLevel(root, i); 
} 
  
/* Print nodes at a given level */
void printGivenLevel(node* root, int level) 
{ 
    if (root == NULL) 
        return; 
    if (level == 1) 
        cout << root->data << " "; 
    else if (level > 1) 
    { 
        printGivenLevel(root->left, level-1); 
        printGivenLevel(root->right, level-1); 
    } 
} 
  
/* Compute the "height" of a tree -- the number of 
    nodes along the longest path from the root node 
    down to the farthest leaf node.*/
int height(node* node) 
{ 
    if (node == NULL) 
        return 0; 
    else
    { 
        /* compute the height of each subtree */
        int lheight = height(node->left); 
        int rheight = height(node->right); 
  
        /* use the larger one */
        if (lheight > rheight) 
            return(lheight + 1); 
        else return(rheight + 1); 
    } 
} 

有些code可以參考一下做法，滿受用的

這個做法也是一層一層的印，不過有點麻煩的是要先知道level是多少

 

大概解紹了幾種tree traversal的方法，中間參考了很多別的網站上的介紹

主要還是要有辦法內化成自己的東西啦，或是把其中的一些概念應用到別的地方

希望能夠藉由記錄來讓自己印象更深刻，那就這樣了~

arrow
arrow
    全站熱搜
    創作者介紹
    創作者 頁頁頁六滴 的頭像
    頁頁頁六滴

    人森很精彩，所以要把所有事情都記起來=ˇ=

    頁頁頁六滴 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄