题目内容
(请给出正确答案)
[单选题]
一棵二叉树的前序遍历序列为ABCDEFG,它的中序遍历序列可能是()。
A.CABDEFG
B.ABCDEFG
C.DACEFBG
D.ADCFEGB
答案
(1) (2)设二叉树的前序遍历序列为P1P2…Pm中序遍历序列为S1S2…Sm。因为前序遍历是“根一左一右”中序遍历是“左一根一右”则前序遍历序列中第一个结点P1是根结点。到中序序列中查询到Si=P1根据中序遍历时根结点将中序序列分成左右两部分的原则有:若i=1即S1=P1则这时的二叉树没有左子树;否则S1S2…Si一1是左子树的中序遍历序列用该序列和前序序列p2P3…Pi去构造该二叉树的左子树。若i=m即Sm=P1则这时的二叉树没有右子树;否则Si (1)(2)设二叉树的前序遍历序列为P1,P2,…,Pm,中序遍历序列为S1,S2,…,Sm。因为前序遍历是“根一左一右”,中序遍历是“左一根一右”,则前序遍历序列中第一个结点P1是根结点。到中序序列中查询到Si=P1,根据中序遍历时根结点将中序序列分成左右两部分的原则,有:若i=1,即S1=P1,则这时的二叉树没有左子树;否则,S1,S2,…,Si一1是左子树的中序遍历序列,用该序列和前序序列p2,P3,…,Pi去构造该二叉树的左子树。若i=m,即Sm=P1,则这时的二叉树没有右子树;否则,Si
如搜索结果不匹配,请 联系老师 获取答案