※ 引述《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;
}
換句話說, 這個方法不是把空白當做每個元素之後的結束符號
而是把空白放進整體輸出裡去觀察其規則

這個方法比旗標變數的做法漂亮多了 XDpreorder 跟 postorder 的代碼好像反了 (?還有好像每個函式的開頭缺了 if(!node) return;所以最後可以把 code 整理成：void* printPreorder(struct node* node) {if (node == NULL) return NULL;if (preorderTraverse(node->left)) cout<<" ";if (preorderTraverse(node->right)) cout<<" "cout << node->value; return node; }上面 preorderTraverse 就是 printPreorder 打錯 XD

推推 L大好厲害! 可以從另一個角度去找方法

讚這個應該是標準解答了

推!

其實我看不懂原來文章在問甚麼