关于二叉树的问题，高手来看看（50分相送）

1。在一颗高度小于4的二叉树中，若结点的前序序列是abcdef,则结点的中序序列有可能是：______
A dcebaf  B bcdafe C cbdafe  D fcadbe
2. 若二叉树中结点的中序序列是abcdef,则结点的前序序列不可能是：_____
A dbacef  B acbedf  C efbacd D bafdce
3. 在一颗高度小于5的二叉树中，若结点的中序序列是abcdef,则结点的后序序列有可能是：____
A bdfeca  B befdca  C bdefca D fedcba
4. 已知二叉树中有11个结点，遍历的序列如下：
   前序序列：...b...f...iceh...g
   中序序列：d...kfia...ejc...
   后序序列：...k...fbhj...g...a
  请写出二叉树的中序遍历序列

请问各位高手有没有什么规律可循，在1~2分钟内搞定一题？

20 个解决方案

#1

1.A,C

#2

第二题不符合要求的先序序列有很多，我没有找到好方法来找出它们

#3

#4

1、只可能是C
2、B

#5

第二题如果要从上面四个选项中选的话，我觉得这四个选项都改选，即它们四个都不可能是满足要求的先序序列。

#6

1. B,C

#7

太晚了，明天再做。

#8

2.a,c,d

#9

2. C

#10

3. A

#11

4.
前： a b d f k i c e h j g
中： d b k f i a h e j c g
后： d k i f b h j e g c a

#12

1、该二叉树中总共6个节点，而二叉树的高度少于4，所以只能是一个三层的二叉树，又从前序序列可知，该二叉树根节点为a，所以a左右两侧分别有2个和3个节点。因此，从答案中每个中序序列中a的位置可以首先排除选项a。选项d显然不合理，选项b和c分别画一下，就知道选c了。

我的思考过程有些复杂，如果哪位朋友有更好的方法，望跟帖。

#13

#14

2、C
中序序列 abcdef
前序序列 efbacd

从C选项的前序序列可以断定根节点为e，回头再看中序序列，可知abcd位于e左侧，f位于e右侧，而此时再看前序序列可以发现f位于e左侧，前后推导矛盾，故C选项不可能。

#15

3、A

#16

3、选A。
B不可能，原因同题2。
C、D的树太高。

#17

1, 应选a c 因为该树共有3层,第二层的右子树只能是d或e,则转为中序序列时有4 种可能,古选a c

#18

1,应是 b c 改正

#19

1.A  B  C
由前序序列得a是根结点，然后自己动手画一下就知道了
A                     B                        C

    a                     a                       a
   / \                   / \                     / \
  b   f                 b   e                   b   e
/                       \  /                   /\ /
c                         c f                  c  df
/\                         \
d e                         d

至于D  f在a的左子树，显然在前序遍历时比右子树bde先遍历，与题目不符

2.A B C      与先前思路相反，  每个选择的第一个为根结点，判断一下就可以了

#20

limin(我好笨我好困)
的解法是标准解法

#21

面试中关于二叉树的问题（Java版）

#1