4、已知二叉树的前序和中序遍历序列 列ABCDEFGHIJ和BCDAFEHIJG (1)画出此二叉树 -----5分 (2)试写出该二叉树的后序遍历序列 -----5分 (3)画出该二叉树中序遍历序列的线 索二叉树 -----10分

(1)画出此二叉树：

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

(2)该二叉树的后序遍历序列为：ACEDBHIFJG

(3)画出该二叉树中序遍历序列的线索二叉树：

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

其中，红色实线表示中序遍历的顺序，蓝色虚线表示前驱和后继的指针。

相关问题

某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无右孩子

这个结论是错误的。下面给出一个反例：

前序遍历序列为：1 2 3 4

中序遍历序列为：4 3 2 1

根据前序遍历序列，我们可以得到根结点是1，1的左子树的前序遍历序列为2 3 4，中序遍历序列为4 3 2；1的右子树为空。

根据中序遍历序列，我们可以得到根结点是4，4的左子树为空，4的右子树的前序遍历序列为3，中序遍历序列为3。

可以发现，这个二叉树的前序和中序遍历序列正好一样，但是根结点1有右孩子，所以该二叉树中的任何结点并不一定都无右孩子。

已知二叉树的前序遍历序列是AEFBGCDHIKJ,中序遍历序列是EFAGBCHKIJD,画出此 二叉树

我们可以根据前序遍历和中序遍历的规律来构造这棵二叉树：

1. 前序遍历的第一个元素是根节点，即A。
2. 在中序遍历中，根节点A左侧的所有元素都属于左子树，右侧的所有元素都属于右子树。
3. 由于前序遍历的第二个元素是左子树的根节点，所以我们可以得到左子树的前序遍历序列为EFBG，中序遍历序列为EFGABC.
4. 由于前序遍历的第六个元素是右子树的根节点，所以我们可以得到右子树的前序遍历序列为CDHIKJ，中序遍历序列为CHKIGDJB。

根据上述规律，我们可以递归构造出这棵二叉树，如下图所示：

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

其中，蓝色节点表示前序遍历序列中的节点，红色节点表示中序遍历序列中的节点。