如果一个二叉树后序和中序序列都为abcdefgh，这个二叉树长什么样

如果一个二叉树的后序和中序遍历序列都是abcdefgh，那么我们可以根据这两个序列来还原出这棵树的结构。由于后序遍历的顺序是左子树、右子树、根节点，而中序遍历的顺序是左子树、根节点、右子树，因此我们可以通过这两个序列来找到根节点和子树的结构。

首先，后序遍历的最后一个元素h是树的根节点。在中序遍历序列中，我们可以找到h，并将其分割成两部分，左边的元素是左子树的中序遍历结果，右边的元素是右子树的中序遍历结果。由于后序遍历是先左后右，我们可以得知左子树比右子树多一个节点（因为根节点已经在左子树中计算过了）。

现在，我们可以按照后序和中序遍历的元素数量来分割后序序列。由于h是根节点，那么左子树的后序遍历结果将包含左中序遍历结果中的所有元素，右子树的后序遍历结果包含右中序遍历结果的所有元素。因此，我们可以将后序序列分为两部分，前半部分是左子树的后序遍历结果，后半部分（除去根节点h）是右子树的后序遍历结果。

这样，我们就可以递归地对左子树和右子树进行相同的操作。最终，我们会发现这棵树是一个完全不平衡的二叉树，其结构如下：

        h
       /
      g
     /
    f
   /
  e
 / \
d   c
    \
     b
      \
       a

这棵树中，每个节点都只有右子节点，没有左子节点，所以这实际上是一条向左的链。

相关问题

已知二叉树先序ABCDEFGH,和中序DCEBAFGH,二叉树后序序列

已知二叉树的先序遍历顺序是 ABCDEFGH，中序遍历顺序是 DCEBAGHF，我们可以利用这两个线索重建这颗二叉树。

先序遍历的特点是根节点在前，左子树在右子树之前。所以，A肯定是树的根节点。接下来，我们在中序遍历中找到A的位置，它左边的部分DCEB是左子树的中序遍历，右边部分AGHF是右子树的中序遍历。

中序遍历的特点是左子树先，根节点在中间，右子树后。因此，DCEB是左子树的中序遍历，说明D是左子树的根，E和B在其左侧，C在其右侧。同样，AGHF是右子树的中序遍历，G在F和H之间，A在G前面，H在G后面。

根据上述信息，可以构建出这样的二叉树结构：

       A
      / \
     D   G
    / \ / \
   C  E F H

最后，由于后序遍历是左、右子树后跟根节点，对于这个二叉树，其后序遍历应该是EHGFDCBA。

设一棵二叉树的先序序列为ABCDEFGH，中序序列为BFDAGEHC，画出这颗二叉树

根据给出的先序遍历(Preorder)序列ABDEFGCH和中序遍历(Inorder)序列BFADGEHC，我们可以推断出该二叉树的结构。因为中序遍历的特点是左子节点 -> 根节点 -> 右子节点，所以根节点通常位于中序序列的中间部分。

首先，我们从中序序列找到根节点B，它出现在B、F、A、D之间，所以根节点B应该连接两个子树，左子树的中序遍历应该是BDAG，右子树则是EFHC。

现在我们继续分析：

- 先序序列的A对应于根节点B的左子树的第一个元素，所以我们可以在B的左边添加一个左子树，其先序遍历是ADE，这意味着根节点B的左子树的根是A，左子树的剩余部分是DE。
- 中序遍历的D紧跟在A之后，说明它是A的左子节点；E位于D和A之间，是A的右子节点。

接下来，对于右子树：

- 先序序列的F紧跟在根节点B之后，所以它是B的右子节点。
- G位于F和H之间，说明它是F的右子节点。
- H作为叶子节点，直接放在G的右边。

综上所述，这棵二叉树可以这样画出来：

          B
        /     \
       A      F
      / \     / \
     D   E  G   H