作者MarkHero (Mark)
看板TransCSI
标题[问题] 关於二元树的前序、中序、後序追踪法
时间Tue Apr 12 14:39:38 2011
最近开始读到演算法的基础东西了，
但是对这从来没碰过的东西总是非常陌生，
特别是最近看到的前序、中序、後序追踪的部分，
前序追踪法我看了很久才搞懂他的逻辑，
但中序就越来越难懂了，上网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也没问题!!!!!
麻烦各位前辈帮我用简单一点的方式解释一下中序跟後序的规则....
我不想在这里就浇熄我对资工的热情阿!!!!!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.57.64.233
※ MarkHero:转录至看板 ask 04/12 14:40
1F：推 nosignal90:我是把它们都变成最小单位的三角形,当初也研究好久XD 04/12 19:05
2F：推 windverb:你可以用画线的方式来围绕整个树 04/13 17:39
3F：→ windverb:1.用中序的话就在每个节点画↓的箭头 04/13 17:41
4F：推 windverb:2.由左往右画一条每个节点都会经过的线 04/13 17:43
5F：→ windverb:画法像你把手掌贴在纸上画轮廓一样 04/13 17:44
6F：→ windverb:这样一直从树根左边画回树根右边 04/13 17:44
7F：→ windverb:画的线都都要经过每个节点下方的箭头 04/13 17:46
8F：→ windverb:照顺序从左边开始判断每个被经过的节点就是中序了 04/13 17:47
9F：→ windverb:抱歉用讲得很难让人明白= = 04/13 17:47
10F：推 EEspresso:还有一种方法是用 遇到了几次在解 的 我们资结老师有教 04/15 00:09
11F：推 EEspresso:比较简单的理解方法 就是tree用逆时针画一圈 遇到一次就 04/15 00:12
12F：→ EEspresso:标上1 遇到第2次标上2 遇到第3次标上3 然後preorder就是 04/15 00:14
13F：→ EEspresso::第一次遇到依逆时针列出 inorder:第二次遇到的列出 04/15 00:15
14F：→ EEspresso:postorder:就是最後一次遇到的列出 不过我都没照这个xd 04/15 00:16