鱼C论坛

 找回密码
 立即注册
查看: 3587|回复: 10

谁给我讲讲二叉树的遍序 啊?/马上二级就来了,唉

[复制链接]
发表于 2011-3-17 22:16:26 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
我知道二叉树的
中序
1)遍历左子树; (2)访问根结点; (3)遍历右子树。
先序
(1) 访问根结点; (2) 遍历左子树; (3) 遍历右子树。
后序
(1)遍历左子树; 2)遍历右子树; (3)访问根结点
但是感觉有时候在不同的遍序里面左子树里面的排序又似乎各不一样,谁给我讲讲啊
给个题目做例子:已知二叉树中序遍历序列是dbeafc,前序遍历序列是abdecf,它的后序遍历序列是____
{:2_33:}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-3-17 23:33:39 | 显示全部楼层
zhidao.baidu.com/question/214927879.
html
这个帖子的满意答案我觉得方法说得很好。。
我的回答是下面的那个二楼!有分割线那个。。。。
希望对你有帮助。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-3-17 23:44:35 | 显示全部楼层
回复 2# 风扫地


    你的那个链接我看了,不过不懂你的那个()算法是什么得来的,
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-3-18 00:49:49 | 显示全部楼层
回复 3# 的的
那个满意答案是我下面的文字描述的简化形式。。。
如果看不懂怎么表示,就先看我的文字描述,然后在看那个()的..有分割线的那个答案就是我的文字描述。。。。
..
其实没有被()的就是被判断出来为根节点的节点。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-3-18 02:07:07 | 显示全部楼层
画一个二叉树!
  沿着根节点走(先左后右):第一次返问到得记下来!这样的就是先序!
                              第二次返问到得记下来!这样的就是中序!
                              第三次返问到得记下来!这样的就是后序!
                            ( 没有前驱的补上来)。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-3-18 19:28:02 | 显示全部楼层
楼主,不必太担心。我们也要考二级,老师也根本没讲那个东东。而且据上几届的学长所说,二级都是些简单东西啦。多注意点平常学的东西就够了,淡定!最后祝你顺利过二级啊!我也一样要过
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-3-19 21:18:08 | 显示全部楼层
本帖最后由 仓小姐 于 2011-3-19 21:53 编辑

回复 1# 的的


.                      a
                    /     \
                  b        c
                /   \      /
              d     e    f
你要的树是这样的,然后求后序:

我的思考过程如下,一定要有递归的思想:
1.前序遍历abdecf,前序是根左右,那么a肯定是某树的根
2.中序遍历dbeafc,中序是左根右,那么可以得到树
.                     a
                    /     \
                dbe      fc
3.判断左子树dbe,看题目里面dbe的排列情况,递归用1.2.的算法   我再写一遍
   前序遍历bde,根左右,b肯定是某树的根
   前序遍历dbe,左根右,可得到树
.                      b
                    /     \
                  d       e
   -------------------------------
    那么这时候可以判断树是这样子的:
.                      a
                    /     \
                  b        fc
                /   \     
              d     e   
4.同理判断右子树fc,也是递归用1.2.的算法不用我写了吧,

晕死,这样排版累死我了,你看懂了怎么也得给我一个好评
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-3-21 08:51:42 | 显示全部楼层
回复 6# 故乡的风


    希望如此咯,不过这个事实上是要考的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-3-21 08:56:20 | 显示全部楼层
回复 7# 仓小姐


    {:2_37:} 哈哈,我懂了、、原来每一层都要按照那个左根右来啊,哈哈、、
膜拜仓老师,虽然咱一直没咋关注那些个东西
感谢感谢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 2011-3-21 10:23:07 | 显示全部楼层
回复 7# 仓小姐
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2014-3-17 11:22:42 | 显示全部楼层
一层一层看啥,很容易的,根据先序一下子就得到根节点,就是先序的第一个数啥如a,然后再看中序,找到a的位置,这样已a为分界点,左边是左子树,右边是右子树,然后再看先序,这样一次类推!!!!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-25 01:55

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表