2、设一棵二叉树的中序遍历序列为DCBGEAHFIJK和后序遍历序列为DCEGBFHKJIA。 1) 画出该二叉树 2) 二叉树的深度 3) 画出该二叉树顺序存储结构 4) 画出他的扩展二叉树

1) 二叉树如下图所示：

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

2) 二叉树的深度为4。

3) 该二叉树的顺序存储结构如下表所示：

节点 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13
-----|---|---|---|---|---|---|---|---|---|---|---|---|---
元素 | A | B | C | D | E | G | H | I | J | K | F | G | H

其中，节点i的左孩子为节点2i，右孩子为节点2i+1。

4) 扩展二叉树如下图所示：

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

其中，红色的节点表示原二叉树中的节点，蓝色的节点表示新加入的节点，绿色的节点表示扩展二叉树中省略的节点。

相关问题

假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA。请： (1)画出该二叉树；

好的，根据中序序列和后序序列可以还原出该二叉树，具体步骤如下：

1. 后序序列的最后一个元素J为该二叉树的根节点；
2. 在中序序列中找到J，可以将中序序列划分为左子树和右子树，即DCBGEAHFIK和IJ；
3. 对于左子树DCBGEAHFIK，其后序序列为DCEGBFHKIA，其中最后一个元素A为左子树的根节点；
4. 在左子树中，中序序列中A的左边为左子树，右边为右子树，即DCBGEHFI和K；
5. 对于左子树DCBGEHFI，其后序序列为DCEGBFHK，其中最后一个元素F为左子树的根节点；
6. 在左子树中，中序序列中F的左边为左子树，右边为右子树，即DCBG和EHFI；
7. 对于左子树DCBG，其后序序列为DCEGB，其中最后一个元素G为左子树的根节点；
8. 在左子树中，中序序列中G的左边为左子树，右边为右子树，即DCB和E；
9. 对于左子树DCB，其后序序列为CEG，其中最后一个元素B为左子树的根节点；
10. 在左子树中，中序序列中B的左边为左子树，右边为右子树，即DC和G；
11. 对于左子树DC，其后序序列为CE，其中最后一个元素C为左子树的根节点；
12. 对于右子树EHFIK，其后序序列为GBFHKIA，其中最后一个元素A为右子树的根节点；
13. 在右子树中，中序序列中A的左边为左子树，右边为右子树，即EHFI和K；
14. 对于左子树EHFI，其后序序列为GBFHK，其中最后一个元素I为左子树的根节点；
15. 在左子树中，中序序列中I的左边为左子树，右边为右子树，即EHF和K；
16. 对于左子树EHF，其后序序列为GBFH，其中最后一个元素H为左子树的根节点；
17. 在左子树中，中序序列中H的左边为左子树，右边为右子树，即EF和K；
18. 对于左子树EF，其后序序列为GBF，其中最后一个元素F为左子树的根节点；
19. 在左子树中，中序序列中F的左边为左子树，右边为右子树，即E和K；
20. 对于左子树E，其后序序列为G，其中最后一个元素E为左子树的根节点；
21. 对于右子树K，其后序序列为BFIHGA，其中最后一个元素A为右子树的根节点；
22. 在右子树中，中序序列中A的左边为左子树，右边为右子树，即K和BFIHG；
23. 对于右子树BFIHG，其后序序列为GBFIH，其中最后一个元素G为左子树的根节点；
24. 在左子树中，中序序列中G的左边为左子树，右边为右子树，即BF和IH；
25. 对于左子树BF，其后序序列为GIH，其中最后一个元素F为左子树的根节点；
26. 在左子树中，中序序列中F的左边为左子树，右边为右子树，即B和G；
27. 对于左子树B，其后序序列为G，其中最后一个元素B为左子树的根节点；
28. 对于右子树IH，其后序序列为BFI，其中最后一个元素I为右子树的根节点；
29. 在右子树中，中序序列中I的左边为左子树，右边为右子树，即H和BF；
30. 对于左子树H，其后序序列为F，其中最后一个元素H为左子树的根节点；
31. 对于右子树BF，其后序序列为GI，其中最后一个元素F为右子树的根节点；
32. 在右子树中，中序序列中F的左边为左子树，右边为右子树，即B和G；
33. 对于右子树GI，其后序序列为BF，其中最后一个元素I为右子树的根节点；
34. 在右子树中，中序序列中I的左边为左子树，右边为右子树，即G和B。

根据以上步骤可以画出该二叉树如下所示：

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

其中，每个节点的左子树中序遍历序列的顺序与右子树中序遍历序列的顺序不重复。

已知二叉树中序遍历序列为CBDFEGAMLNKJOPRQIHS， 后序遍历序列为CFGEDBMNLKRQPOJISHA，试画出此二叉树

根据二叉树遍历的特点，可以确定该二叉树的根节点为序列中的最后一个节点 "A"。然后在中序遍历中找到根节点的位置，根节点左边的序列为左子树的中序遍历序列，右边的序列为右子树的中序遍历序列。同样，在后序遍历中，根节点左边的序列为左子树的后序遍历序列，右边的序列为右子树的后序遍历序列。然后递归构造左右子树即可。

构造过程如下：

1. 根据中序遍历序列，确定根节点为 "A"，并找到 "A" 在中序遍历序列中的位置。

2. 根据后序遍历序列，确定根节点为 "A"，并找到 "A" 在后序遍历序列中的位置。

3. 根据中序遍历序列和后序遍历序列，确定左子树的中序遍历序列为 "CBDFEGM"，左子树的后序遍历序列为 "CFGEDBM"。

4. 根据中序遍历序列和后序遍历序列，确定右子树的中序遍历序列为 "LNKJOPRQIHS"，右子树的后序遍历序列为 "NLKRQPOJISH".

5. 递归构造左右子树，得到完整的二叉树。

最终的二叉树如下图所示：

          A
        /   \
       /     \
      /       \
     /         \
    C           L
   / \         / \
  /   \       /   \
 B     D     K     N
      / \         / \
     /   \       /   \
    F     E     J     O
         / \           \
        /   \           \
       G     M           I
                          \
                           \
                            S

其中，节点的左子树在上方，右子树在下方。