已知一棵二叉树的先序遍历序列为ABCDEFGHIJ,中序遍历序列为CBDEAFHIGJ.

已知一棵二叉树的先序遍历序列为ABCDEFGHIJ,中序遍历序列为CBDEAFHIGJ.试构造这棵二叉树,要求写出构造过程步骤

第1个回答  2015-06-26
先看先序,其第一个为树的根,先序遍历是先根再左子树最后右子树,第一个肯定是树的根,先画A,A再中序遍历中左右都有,说明A有左子树也有右子树。

A
/ \
然后看先序第一个值是B,在中序中为A的前面,所以B是A的左子树
A
/ \
B
继续看先序,接下来是C、D,C再中序中再B的前面,所以C是B的左子树,D在B后面,D是B的右子树。
A
/ \
B
/ \
C D
接下来是E,E在中序是在D后面A前面,所以E是D的右子树
A
/ \
B
/ \
C D
\
E
接着先序中是F,F在中序为A后面,是A的右子树
A
/ \
B F
/ \
C D
\
E
中序中 A 与F之间没有,说明F没有左子树,只有右子树.如上面方法继续分析GHIJ,最终二叉树如下:
A
/ \
B F
/ \ \
C D G
\ / \
E H J
\
I本回答被网友采纳
第2个回答  2018-01-07
1 答案不唯一
2 e位置错误
相似回答