楼上的说的不准确,只给先、后,不一定可以确定一棵树,你给的就不行
先根:根-左-右
后根:左-右-根
因此,由先根次序访问序列为GFKDAIEBCHJ,可以确定,第一个G即为树根节点
设二叉树表示为:
G
/ \
{左儿子集合} {右儿子集合}
从先后根的定义就可以知道:
先根序列G后面那个就是{左儿子集合}的根
后根序列G前面那个就是{右儿子集合}的根
所以有:
G
/ \
F B
/ \ / \
{...} {...} {...} {...}
而先序中F与B之间的GF{KDAIE}BCHJ,同时也是后序序列F之前的{DIAEK}FCJHBG,
就是F的儿子
而先序中B之后的GFKDAIEB{CHJ},同时也是前序序列F与B之间的DIAEKF{CJH}BG
就是B的儿子
然后问题就转化成了两个子问题:
一、
前序为:FKDAIE
后序为:DIAEKF
的树是啥样?
二、
前序为:BCHJ
后序为:CJHB
的树是啥样?
之所以说光依靠先后序列不一定能推出来,是因为假如一个节点只有一个儿子,那么以这个儿子为根的所有子节点无论是在左边,或是在右边,它们的先序、后序序列都是一样的(先序的话一定在根后面,后续的话一定在根前面)
如果不存在单儿子节点,那么按照以上方法递归下去,结果就出来了,但是你给的我推了一下,有矛盾
已知前序和后序不能确定一棵二叉树啊!不能确定啊!!