為什麼這篇cout空格鄉民發文收入到精華區:因為在cout空格這個討論話題中,有許多相關的文章在討論,這篇最有參考價值!作者LPH66 (かつて交わした約束)看板C_and_CPP標題Re: 關於tree travers...
※ 引述《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
!node 其實也能寫在前一層, 少一個判斷但這樣就不能丟空樹進去了
(變成像
if(node->left != nullptr)
{
cout << " ";
preorderTraverse(node->left);
}
這種樣子)
※ 編輯: LPH66 (123.195.9.46), 11/19/2017 11:47:09