全部问题 > 当前问题

这题的二叉树图是什么样的,推不出来。。。。


韦廷源 2018-2-9 08:46:34

共 1 个回答

绅士 2018-4-3 12:07:03

首先,我表示这是我的个人理解,如有误,请纠正,谢谢。

我推了下,应该是这样子的。根节点是A,且只有左子树,这点很好判断。

按我的图,先看中序:左中右,就是左边全部算完才能算其他的。A的左边为B,B的左边没有数,中间是B(记下第一个数B);然后开始算B的右边C,C的左边是D(记下第二个数D),C的中间就是C(记下第三个数C),右边没有数;此时A的左边全部算完,A的中间就是A,所以中序就是BDCA。

后序:左右中,此时要左边全部算完和右边全部算完后才能算中间。A的左边是B,B的左边没有(完),B的右边是C,还没完,因为C 的左边有数D,所以我们就算D;D的左右都没数,中间就是D(第一个记下D);D算完了,可以算C的了,以此类推。记住要全部算完才能下一步!

屏幕截图.png


问题来自: 二叉树的遍历
某二叉树的中序序列为BDCA,后序序列为DCBA,则前序序列为( )
A. DCBA
B. BDCA
C. ABCD
D. BADC
答案:C
解析:后序序列是左右中,根结点为A;中序序列是左中右,二叉树只有左子树。按照遍历的顺序规则排列得出前序序列为ABCD。所以选择C。