c*********t
发帖数: 2921 | 1 1. 如何用iterative 的方法实现postorder遍历binary tree？
recursive的方法太简单了。
好像inorder, preorder的iterative比较容易用stack就行了。可是postorder,我想不
出好的方法。谁能给个pseudo code?
2. 给定postorder 和 inorder遍历的结果，想个算法还原出binary tree.
3. 给定preorder 和 inorder遍历的结果，想个算法还原出binary tree.
我有三个包子，谁给回答对，就发包子给谁，一个包子一题。
给出pseudo code就行了。
谢谢！ |
g*******y
发帖数: 1930 | 2 才三个包子。。。
我以前贴过用stack实现postorder的code
你搜一下呢
重建树的时候，postorder数组的最后一个是根，在inorder数组中搜索到这个根，
inorder数组中左边的就是左子树的集合，右边就是又子树。
两边子树的集合就确定下来了。递归的建立左子树，柚子树，再跟当前的根连接起来就
行了。 |
c*********t
发帖数: 2921 | 3 咳，我穷呀。总共只有三个包子了。现在给你发两个。请笑纳！
【在 g*******y 的大作中提到】
: 才三个包子。。。
: 我以前贴过用stack实现postorder的code
: 你搜一下呢
: 重建树的时候，postorder数组的最后一个是根，在inorder数组中搜索到这个根，
: inorder数组中左边的就是左子树的集合，右边就是又子树。
: 两边子树的集合就确定下来了。递归的建立左子树，柚子树，再跟当前的根连接起来就
: 行了。
|
g*******y
发帖数: 1930 | 4 呵呵，笑纳了～
我还以为一个包子就是一个伪币，原来是10个，还不错，呵呵~
【在 c*********t 的大作中提到】
: 咳，我穷呀。总共只有三个包子了。现在给你发两个。请笑纳！
|
c*********t
发帖数: 2921 | 5 如果你多多回答问题，我就去借伪币，在发给你。呵呵！
还有一个愚蠢的问题，请别见笑，你多次在回答别的问题时提到 backtracking的方法
，我找了 CLR 的算法导论的书，好像没有提到过这个算法呀？什么书讲过这个算法？
谢谢！
【在 g*******y 的大作中提到】
: 呵呵，笑纳了～
: 我还以为一个包子就是一个伪币，原来是10个，还不错，呵呵~
|
g*******y
发帖数: 1930 | 6 呵呵，其实我也是新手，前几天才学的backtracking，用来做一些状态空间搜索的问题
比较普适的。
我是自己看的一个中文的算法书，估计你找不到。不过你可以在网上搜搜
"回溯法 剪枝"
另外就是我知道刘汝佳的那本算法竞赛的书里面有讲的，不过不知道那本书对新手会不
会太难了一些
【在 c*********t 的大作中提到】
: 如果你多多回答问题，我就去借伪币，在发给你。呵呵！
: 还有一个愚蠢的问题，请别见笑，你多次在回答别的问题时提到 backtracking的方法
: ，我找了 CLR 的算法导论的书，好像没有提到过这个算法呀？什么书讲过这个算法？
: 谢谢！
|
m*****f
发帖数: 1243 | 7
1. curr = prev = root
2. Initialize stack
3. while (true)
4. if ( curr is prev or a child of prev) //Traversing downwards
5. if (curr is a parent) //More traversing to do
6. stack.push(curr)
7. prev = curr
8. curr = curr.left
9. else //curr is an orphan: go upward
10. print (curr)
11. prev = curr
12. curr = stack(top)
13. if ( curr.left = prev) //Traversing upwa
【在 c*********t 的大作中提到】
: 1. 如何用iterative 的方法实现postorder遍历binary tree？
: recursive的方法太简单了。
: 好像inorder, preorder的iterative比较容易用stack就行了。可是postorder,我想不
: 出好的方法。谁能给个pseudo code?
: 2. 给定postorder 和 inorder遍历的结果，想个算法还原出binary tree.
: 3. 给定preorder 和 inorder遍历的结果，想个算法还原出binary tree.
: 我有三个包子，谁给回答对，就发包子给谁，一个包子一题。
: 给出pseudo code就行了。
: 谢谢！
|
