如图所示二叉树的中序序列是()

            A
          /   \
        B      C
       / \    / \
      D   E  F   G
         /      /
        H      I
              /
             J

A. DHEBAFIJCG

B. DHEBAFJICG

C. DBHEAFCJIG

D. DBHEAFJICG

参考答案 C

比较简单，画图演算可得C正确。

二叉树的( )第一个访问的结点是根结点

A. 先序遍历

B. 中序遍历

C. 后续遍历

D. 以上都是

参考答案 A

前序遍历序列与中序遍历序列相同的二叉树为( )

A. 根结点无左子树的二叉树

B. 根结点无右子树的二叉树

C. 只有根结点的二叉树，或非叶子结点只有左子树的二叉树

D. 只有根结点的二叉树，或非叶子结点只有右子树的二叉树

参考答案 D

前序和中序相同，肯定是没有左子树的。

如果一颗二叉树的中序遍历是BAC，那么它的先序遍历不可能是( )

A. ABC

B. CBA

C. ACB

D. BAC

参考答案 C

穷举法

 	A            B                    C             C
 B	   C            A              A             B
                       C        B                   A

ABC BAC CAB CBA

已知二叉树的中序遍历为DEGHFCABI，后序遍历为HGFEDCIBA，则该二叉树的前序遍历为( )

A. ABCDEFGHI

B. ACDEFHGBI

C. ADCEFGHBI

D. ACDEFGHBI

参考答案 D

中序遍历和后续遍历构造出二叉树，得到前序遍历：

• 先根据后续遍历，找到根结点，比如A；

• 通过根结点和中序遍历，构造二叉树的左右子树；

• 依次递归每个子树即可；

画图演算

已知7个结点的二叉树的先序遍历是1 2 4 5 6 3 7，中序遍历是4 2 6 5 1 7 3，则该二叉树的后序遍历是( )

A. 4 6 5 2 7 3 1

B. 4 6 5 2 1 3 7

C. 4 2 3 1 5 4 7

D. 4 6 5 3 1 7 2

参考答案 A

先序和中序遍历，构造二叉树，得到后续遍历：

• 现根据前序遍历，找到根结点，比如1

• 通过根结点和中序遍历，构造二叉树的左右子树；

• 依次递归每个子树即可；

画图演算

算术表达式 a+b*(c+d/e) 转换为后缀表达式后为( )

A. ab+cde/*

B. abcde/+*+

C. abcde/*++

D. abcde*/++

参考答案 B

方法一：构造成二叉树（画图演算）

方法二：小括号法 (a+(b*(c+(d/e))))

• (a+(b*(c+(de/))))

• (a+(b*(cde/+)))

• (a+(bcde/+*))

• (abcde/+*+)

前缀表达式 *+234 的计算结果是()

A. 24

B. 20

C. 18

D. 14

参考答案 B

小括号法：(*(+23)4)

• (*(2+3)4)

• (2+3)*4