已知一棵二叉树的后序序列ECGHFDBA和中序序列ECBDGFHA求这棵二叉树

为了确定这棵二叉树的结构，我们可以利用二叉树的后序遍历（Postorder）和中序遍历（Inorder）的特点。

后序遍历的顺序是左子树 -> 右子树 -> 根节点，而中序遍历的顺序是左子树 -> 根节点 -> 右子树。通过这两个序列，我们可以重建树的过程：

1. 后序遍历的最后一个元素是根节点，所以根节点是 'A'。
2. 中序遍历中，'E' 作为第一个字符出现，说明它是左子树的第一个节点，也是根节点的左孩子。
3. 接着，我们找到 'E' 在中序遍历中第一次出现的位置，它之前的部分（CBGDH）就是它的左子树的后序遍历。后序遍历中下一个元素是 'C'，所以在左子树中，'C' 将成为新的根节点。
4. 我们继续这个过程，在 'C' 的中序遍历部分找到 'B' 和 'D'，它们是 'C' 的左子树和右子树。
5. 对于 'D'，我们同样找到其后继 'H'，并在剩余的后序遍历中找到 'F'，'F' 是 'D' 的右子树。
6. 最后，'B' 没有其他兄弟节点，因为剩下的元素只有 'G'，并且 'G' 应该在 'F' 的右侧，形成 'F' 的右子树。

因此，这棵树可以表示为：

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

相关问题

已知二叉树的后序和中序序列如下，构造出该二叉树，写出它的先序遍历序列。 后序序列：HGFDCEBA 中序序列：EHFGCDBA

根据二叉树的后序遍历序列，可以知道最后一个元素是根节点，即A。然后在中序遍历序列中找到根节点A的位置，可以将中序遍历序列分为左右两个子树的序列：左子树序列为EHFGC，右子树序列为DB。接着，根据左右子树序列的长度，可以将后序遍历序列也分为左右两个子树的序列：左子树序列为HGFDCE，右子树序列为空。这样，就可以递归地构造出整个二叉树。

构造出的二叉树如下所示：

        A
       / \
      /   \
     /     \
    /       \
   EHFGC     DB

它的先序遍历序列为：AEHFGCDB。

已知二叉树先序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。