Re: 關於tree traversal

看板C_and_CPP作者 (かつて交わした約束)時間6年前 (2017/11/19 10:23), 6年前編輯推噓5(5推 0噓 9→)
留言14則, 5人參與, 6年前最新討論串2/2 (看更多)
※ 引述《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
推
11/19 11:13, 6年前 , 1F
這個方法比旗標變數的做法漂亮多了 XD
11/19 11:13, 1F
→
11/19 11:14, 6年前 , 2F
preorder 跟 postorder 的代碼好像反了 (?
11/19 11:14, 2F
→
11/19 11:16, 6年前 , 3F
還有好像每個函式的開頭缺了 if(!node) return;
11/19 11:16, 3F
→
11/19 11:18, 6年前 , 4F
所以最後可以把 code 整理成：
11/19 11:18, 4F
→
11/19 11:20, 6年前 , 5F
void* printPreorder(struct node* node) {
11/19 11:20, 5F
→
11/19 11:20, 6年前 , 6F
if (node == NULL) return NULL;
11/19 11:20, 6F
→
11/19 11:22, 6年前 , 7F
if (preorderTraverse(node->left)) cout<<" ";
11/19 11:22, 7F
→
11/19 11:23, 6年前 , 8F
if (preorderTraverse(node->right)) cout<<" "
11/19 11:23, 8F
→
11/19 11:23, 6年前 , 9F
cout << node->value; return node; }
11/19 11:23, 9F
→
11/19 11:25, 6年前 , 10F
上面 preorderTraverse 就是 printPreorder 打錯 XD
11/19 11:25, 10F
咦真的反了www 偷改一下 !node 其實也能寫在前一層, 少一個判斷但這樣就不能丟空樹進去了 (變成像 if(node->left != nullptr) { cout << " "; preorderTraverse(node->left); } 這種樣子) ※ 編輯: LPH66 (123.195.9.46), 11/19/2017 11:47:09
推
11/19 17:15, 6年前 , 11F
推推 L大好厲害! 可以從另一個角度去找方法
11/19 17:15, 11F
推
11/20 02:17, 6年前 , 12F
讚這個應該是標準解答了
11/20 02:17, 12F
推
11/20 02:37, 6年前 , 13F
推!
11/20 02:37, 13F
推
11/26 23:29, 6年前 , 14F
其實我看不懂原來文章在問甚麼
11/26 23:29, 14F
‣ 更多 LPH66 的文章
文章代碼(AID): #1Q4EibOJ (C_and_CPP)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共2篇)
‣ 更多 LPH66 的文章
文章代碼(AID): #1Q4EibOJ (C_and_CPP)