作者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/cn.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