面试题65（树，图）

B.gfedcba

C.bcdefga

D.bceadfg

正确解析如下：

根据二叉树遍历原则，前序遍历是根左右，中序遍历是左根右，后序遍历是左右根。如果前序遍历二叉树值为abcdefg,那么a一定是根，这样我们再来看选项D,如果bceadfg 是中序遍历，那么bce在左，a 为根，dfg在右。那么根据前序遍历，bce就一定在dfg 左边，所以前序遍历二叉树值不可能为abcdefg.

正确答案在下面

面试例题2 :Which of the following data sequence (s) should NOT produces a balanced binary search tree if the inserted from left to right?

A.8- 1,6,7,4,3,-2

B.20,10,16,4,30,24,31

C.7,12,3,-2,8,19,5,10

D.10,5,20,6,2,1,22,15,30

正确解析如下：

平衡二叉树(Balanced Binary Tree) 具有以下性质，它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。按照这个原则衡量如下二叉搜索树，显然A选项不符合要求。

正确答案在下面

面试例题1的正确答案:D

面试例题2的正确答案:A