已知遍历某二叉树后的中根遍历序列CDBAFGEIEI 和后根遍历序列DCBGFUITEA，试画出该二叉树。

根据给定的中根遍历序列CDBAFGEIEI和后根遍历序列DCBGFUITEA，我们可以推断出节点的顺序。中根遍历是从根开始，先左子树再右子树，而后根遍历则是从叶子节点开始，逆序到根。

首先，让我们根据后根遍历构建底部的节点。后根遍列中有 'D', 'C', 'B', 'G', 'F', 'U', 'T', 'I', 'E', 'A'。这些就是叶节点，按照倒序排列：

          D
       /     \
      C       G
     / \     / \
    B   F U   T
           / \
          I   E
                 \
                  A

接着，我们使用中根遍历的顺序来确定每个节点的位置。中根遍历CDBAFGEIEI告诉我们，'C' 应该是根节点，然后是它的两个子节点 'B' 和 'A'。'F' 是 'B' 的左子节点，'G' 是 'B' 的右子节点。'E' 和 'I' 分别是 'G' 和 'F' 的右子节点。最后，'U' 是 'G' 的另一个右子节点，'T' 是 'U' 的右子节点，'A' 是 'U' 的左子节点。

因此，将这些信息整合起来，得到的二叉树结构是：

        C
       / \
      B   A
     /     \
    F       G
   / \     / \
  I   E   U   T
         / \
        A   E

相关问题

已知一棵树二叉树的先根遍历和中根遍历的序列分别为：ABDGHCEFI和GDHBAECIF，请画出该二叉树，并写出它的后根遍历序列

好的，根据给定的先根遍历和中根遍历，可以画出如下二叉树：

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

此二叉树的后根遍历序列为：DGHBIFECA。

希望我的回答可以帮到您。

已知某二叉树前序遍历序列为 ABDFECGHI 中序遍历序列为 DBEFAGHCI 确定该二叉树结构并画出该二叉树。

已知某二叉树前序遍历序列为 ABDFECGHI，中序遍历序列为 DBEFAGHCI。该二叉树的结构如下所示：

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

建树的C++代码实现如下所示：[^1]

#include<iostream>
#include<cstring>
using namespace std;
struct node{
    char data;
    node* l;
    node* r;
};
node* build(char* pre,char* in,int len){
    node* root(new node);
    memset(root,0,sizeof(node));
    if(len==0) return nullptr;
    root->data=*pre;
    int pos=find(in,in+len,*pre)-in;//查找根节点在中序遍历中的位置
    root->l=build(pre+1,in,pos);//递归构建左子树
    root->r=build(pre+1+pos,in+pos+1,len-pos-1);//递归构建右子树
    return root;
}
void postorder(node* root){//后序遍历打印
    if(root==nullptr) return;
    postorder(root->l);
    postorder(root->r);
    cout<<root->data;
}
int main(){
    char pre[]="ABDFECGHI";
    char in[]="DBEFAGHCI";
    node* root=build(pre,in,strlen(pre));
    postorder(root);
    return 0;
}