[问题] 关于二元树的前序、中序、后序追踪法

楼主: MarkHero (Mark)   2011-04-12 14:39:38
最近开始读到算法的基础东西了,
但是对这从来没碰过的东西总是非常陌生,
特别是最近看到的前序、中序、后序追踪的部分,
前序追踪法我看了很久才搞懂他的逻辑,
但中序就越来越难懂了,上网GOOGLE了一下,
发现:
左→中→右或是左→根→右,是个关键,
但我始终搞不懂一些东西(下面会详述我的问题)
网络上有些大大很厉害,写了一些简易的理解法,
但我却越看越迷糊(可能我理解力或逻辑性蛮差的吧..)
有些特别的记忆法:
1.三人成行(那凑不满三人或是其中一人重复怎办?)
2.儿子摆两边、爸爸放中间(这勉强看得懂)
3.由低到高(这大概是最了解的部分了XD)
4.逐步收纳(有时候最上层反而很快就被收进去,为什么@@?)
我的问题是这样的
A
/  \
B C
/  \ / \
D E F G
/  \  |
H I J
他的中序是这样:HDI B JE A FCG
按照规则来说HDI我是完全没问题,
但B完以后,按照左中右的概念,应该是BAC才对不是吗!?
怎么会突然跳到JE,而且E连结J的地方是直线(书上真的这样画)
直线我要怎么看阿(崩溃!!!)
FCG也没问题!!!!!
麻烦各位前辈帮我用简单一点的方式解释一下中序跟后序的规则....
我不想在这里就浇熄我对资工的热情阿!!!!!
作者: nosignal90 (NoSignal)   2011-04-12 19:05:00
我是把它们都变成最小单位的三角形,当初也研究好久XD
作者: windverb (哈哈哈)   2011-04-13 17:39:00
你可以用画线的方式来围绕整个树1.用中序的话就在每个节点画↓的箭头2.由左往右画一条每个节点都会经过的线画法像你把手掌贴在纸上画轮廓一样这样一直从树根左边画回树根右边画的线都都要经过每个节点下方的箭头照顺序从左边开始判断每个被经过的节点就是中序了抱歉用讲得很难让人明白= =
作者: EEspresso (我要吃!!!)   2011-04-15 00:09:00
还有一种方法是用 遇到了几次在解 的 我们资结老师有教比较简单的理解方法 就是tree用逆时针画一圈 遇到一次就标上1 遇到第2次标上2 遇到第3次标上3 然后preorder就是:第一次遇到依逆时针列出 inorder:第二次遇到的列出postorder:就是最后一次遇到的列出 不过我都没照这个xd

Links booklink

Contact Us: admin [ a t ] ucptt.com