创建二叉树

创建二叉树

时间： 1ms        内存：128M

描述：

已知一颗二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，给出二叉树的树形表示（用括号法）。

输入：

输出：

输出带有括号与字母的用括号法表示的二叉树。

示例输入：

示例输出：

提示：

参考答案（内存最优[0]）：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
typedef char ElemType;
#define SizeMax 205
int max1=0;
typedef struct Node
{
    ElemType data;
    Node* lchild;
    Node* rchild;
} TBNode;
TBNode*bt2(char*post,char *in,int n)
{
    TBNode *b;
    char r,*p;
    int k;
    if(n<=0)return NULL;
    r=*(post+n-1);
    b=(TBNode *)malloc(sizeof(TBNode));
    b->data=r;
    for(p=in;p<in+n;p++)
    if(*p==r)break;
    k=p-in;
    b->lchild=bt2(post,in,k);
    b->rchild=bt2(post+k,p+1,n-k-1);
    return b;
}
void DispTBNode(TBNode*b)
{
    if(b!=NULL)
    {
        printf("%c",b->data);
        if(b->lchild!=NULL||b->rchild!=NULL)
        {
            printf("(");
            DispTBNode(b->lchild);
            if(b->lchild!=NULL)printf(",");
            DispTBNode(b->lchild);
            printf(")");
        }
    }
}
int main()
{
    char a[]={'c','b','e','d','a','h','g','i','j','f'};
   char b[]={'c','e','d','b','h','j','i','g','f','a'};
TBNode *Tree;
Tree=bt2(b,a,10);
DispTBNode(Tree);
    return 0;
}

参考答案（时间最优[0]）：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
typedef char ElemType;
#define SizeMax 205
int max1=0;
typedef struct Node
{
    ElemType data;
    Node* lchild;
    Node* rchild;
} TBNode;
TBNode*bt2(char*post,char *in,int n)
{
    TBNode *b;
    char r,*p;
    int k;
    if(n<=0)return NULL;
    r=*(post+n-1);
    b=(TBNode *)malloc(sizeof(TBNode));
    b->data=r;
    for(p=in;p<in+n;p++)
    if(*p==r)break;
    k=p-in;
    b->lchild=bt2(post,in,k);
    b->rchild=bt2(post+k,p+1,n-k-1);
    return b;
}
void DispTBNode(TBNode*b)
{
    if(b!=NULL)
    {
        printf("%c",b->data);
        if(b->lchild!=NULL||b->rchild!=NULL)
        {
            printf("(");
            DispTBNode(b->lchild);
            if(b->lchild!=NULL)printf(",");
            DispTBNode(b->lchild);
            printf(")");
        }
    }
}
int main()
{
    char a[]={'c','b','e','d','a','h','g','i','j','f'};
   char b[]={'c','e','d','b','h','j','i','g','f','a'};
TBNode *Tree;
Tree=bt2(b,a,10);
DispTBNode(Tree);
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。