作者LPH66 (かつて交わした約束)
看板C_and_CPP
標題Re: 關於tree traversal
時間Sun Nov 19 10:23:31 2017
※ 引述《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://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1511058213.A.613.html
1F：推 Hazukashiine: 這個方法比旗標變數的做法漂亮多了 XD 11/19 11:13
2F：→ Hazukashiine: preorder 跟 postorder 的代碼好像反了 (? 11/19 11:14
3F：→ Hazukashiine: 還有好像每個函式的開頭缺了 if(!node) return; 11/19 11:16
4F：→ Hazukashiine: 所以最後可以把 code 整理成： 11/19 11:18
5F：→ Hazukashiine: void* printPreorder(struct node* node) { 11/19 11:20
6F：→ Hazukashiine: if (node == NULL) return NULL; 11/19 11:20
7F：→ Hazukashiine: if (preorderTraverse(node->left)) cout<<" "; 11/19 11:22
8F：→ Hazukashiine: if (preorderTraverse(node->right)) cout<<" " 11/19 11:23
9F：→ Hazukashiine: cout << node->value; return node; } 11/19 11:23
10F：→ Hazukashiine: 上面 preorderTraverse 就是 printPreorder 打錯 XD 11/19 11:25
咦真的反了www 偷改一下
!node 其實也能寫在前一層, 少一個判斷但這樣就不能丟空樹進去了
(變成像
if(node->left != nullptr)
{
cout << " ";
preorderTraverse(node->left);
}
這種樣子)
※ 編輯: LPH66 (123.195.9.46), 11/19/2017 11:47:09
11F：推 yang20913: 推推 L大好厲害! 可以從另一個角度去找方法 11/19 17:15
12F：推 steve1012: 讚這個應該是標準解答了 11/20 02:17
13F：推 jaid: 推! 11/20 02:37
14F：推 lululun: 其實我看不懂原來文章在問甚麼 11/26 23:29