您现在的位置:小学生自学网>> 信息>> 学习电脑

前序遍历序列为1243576中序遍历序列为4215736

作者: 来源: 发布时间:2011年04月11日 点击数:
 

二叉树T,已知其前序遍历序列为1243576,中序遍历序列为4215736,则其后序遍历序列是( )
A 4257631  B 4275631  C 4275361  D 4723561 E 4526371

自己在大学学过,但不是很熟悉,结果遇到这道最基本的遍历题目还是费了九牛二虎之力才做出,结果还有点错误,最后参考了答案后才恍然大悟,这才记起:前序遍历的顺序是——中左右、中序遍历的顺序是——左中右、后序遍历的顺序是——左右中,看来要恶补这方面的知识了。

 

......1
..../....\
..2.......3
./....../...\
4......5.....6
........\
.........7

根结点为1,则左为42,右5736,再看先根序列24 3576;
左边42在先根序列中以2为先,则1的下一层为2,再看中根序列42,所以4在2的右边;
右边5736在先根序列中以3为先,则3的左边是57,右边是6;
在先根序列中5先于7,在中根序列中7在5的右边;

据此可作上图

再由上图写出后根序列:4275631

答案为:B