※ 引述《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大好厉害! 可以从另一个角度去找方法

赞这个应该是标准解答了

推!

其实我看不懂原来文章在问什么