Re: 關於tree traversal

[LPH66 (かつて交わした約束)]

※ 引述《yang20913 (yanggood)》之銘言：
: preorder, inorder, postorder
: 這三種traversal可以很輕鬆的用recursive來完成
: 以往格式要求都是
: 1(空格)2(空格)3(空格)
: 這樣就印成功了
: 但現在要求
: 1(空格)2(空格)3
: 印出的最後一個元素後面不能接空格
: 想請問要如何判斷哪一個會是最後一個呢
: 目前只想出用大量判斷式
: 但這應該不是個好方法...
有一個可以從遞迴關係中觀察出來的方法:

在這個要求下的輸出的結果其實可以遞迴地表示成

(preorder)  <左子樹結果>_<右子樹結果>_根
(inorder)   <左子樹結果>_根_<右子樹結果>
(postorder) 根_<左子樹結果>_<右子樹結果>

其中 _ 是空白字元

不但如此, 在一個子樹為空的時候它的"對應"空白也不會印出來

(例如僅左樹為空的 preorder 是 <右子樹結果>_根,

 inorder 跟 postorder 是 根_<右子樹結果>, 等等

 這個"對應"很容易能觀察得到就不多說)

那麼我們就可以利用這個觀察來進行列印了:

void preorderTraverse(TreeNode* node)
{
    if(!node) return;
    cout << node->value;
    if(node->left != nullptr) cout << " ";
    preorderTraverse(node->left);
    if(node->right != nullptr) cout << " ";
    preorderTraverse(node->right);
}

void inorderTraverse(TreeNode* node)
{
    if(!node) return;
    inorderTraverse(node->left);
    if(node->left != nullptr) cout << " ";
    cout << node->value;
    if(node->right != nullptr) cout << " ";
    inorderTraverse(node->right);
}

void postorderTraverse(TreeNode* node)
{
    if(!node) return;
    postorderTraverse(node->left);
    if(node->left != nullptr) cout << " ";
    postorderTraverse(node->right);
    if(node->right != nullptr) cout << " ";
    cout << node->value;
}

換句話說, 這個方法不是把空白當做每個元素之後的結束符號

而是把空白放進整體輸出裡去觀察其規則

--
'Oh, Harry, don't you see?' Hermione breathed. 'If she could have done
one thing to make absolutely sure that every single person in this school
will read your interview, it was banning it!'
                      ---'Harry Potter and the order of the phoenix', P513

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.9.46
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1511058213.A.613.html
推 Hazukashiine: 這個方法比旗標變數的做法漂亮多了 XD
→ Hazukashiine: preorder 跟 postorder 的代碼好像反了 (?
→ Hazukashiine: 還有好像每個函式的開頭缺了 if(!node) return;
→ Hazukashiine: 所以最後可以把 code 整理成：
→ Hazukashiine: void* printPreorder(struct node* node) {
→ Hazukashiine:     if (node == NULL)  return NULL;
→ Hazukashiine:     if (preorderTraverse(node->left)) cout<<" ";
→ Hazukashiine:     if (preorderTraverse(node->right)) cout<<" "
→ Hazukashiine:     cout << node->value; return node; }
→ Hazukashiine: 上面 preorderTraverse 就是 printPreorder 打錯 XD
咦真的反了www 偷改一下

!node 其實也能寫在前一層, 少一個判斷但這樣就不能丟空樹進去了

(變成像

 if(node->left != nullptr)
 {
     cout << " ";
     preorderTraverse(node->left);
 }

這種樣子)
※ 編輯: LPH66 (123.195.9.46), 11/19/2017 11:47:09
推 yang20913: 推推 L大好厲害! 可以從另一個角度去找方法
推 steve1012: 讚這個應該是標準解答了
推 jaid: 推!
推 lululun: 其實我看不懂原來文章在問甚麼