2.已知某二叉树的前序遍历序列为5 7 4 9 6 2 1，中序遍历序列为4 7 5 6 9 1 2，则其后序遍历序列为（ ）
A.4 2 5 7 6 9 1

B.4 2 7 5 6 9 1

C.4 7 6 1 2 9 5

D.4 7 2 9 5 6 1

答案：C

解析：

通过前序遍历找到子树的根，在中序遍历中找到根的位置，然后确定根左右子树的区间，即根的左侧为左子树中所有节点，根的右侧为右子树中所有节点。

故：根为： 5

5的左子树：4 7 5的右子树： 6 9 1 2

5的左子树的根为: 7 5的右子树的根为：9

7的左子树: 4 7的右：空 9的左子树：6 9的右子树：2

3.已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为（ ）
A.ABDGHJKCEFILM

B.ABDGJHKCEILMF

C.ABDHKGJCEILMF

D.ABDGJHKCEIMLF

答案：B

解析：

由后序遍历确定子树的根，后序遍历从后向前看，最后一个元素为根，和前序遍历刚好相反，从后向前看后序遍历，应该是根，右，左，根据中序遍历确定子树的左右区间

故：根为: A

A的左子树：JGDHKB A的右子树：ELIMCF

A的左子树的根：B A的右子树的根：C

B的左子树：JGDHK B的右子树：空 C的左子树：ELIM C的右子树：F

B的左子树的根：D C的左子树根：E

D的左子树的根：G D的右子树的根：H E的右子树的根:I

故树的结构为：

A

/ \

B C

/ \ / \

D E G F

\

H

前序遍历
ABDECGFH
中序遍历 左根右
DBEAGCFH

后续
DEBGFHA。

构造二叉排序树，计算二叉排序树平均查找长度。

构造二叉排序树左小右大

计算平均查找长度，比如22在第三层所以比较了三次，40在第四层比较了四次。
ASL=把次数相加在/元素数量得到结果。