由中序序列和後序序列唯一確定一棵二叉樹

NO IMAGE

已知一棵二叉樹的中序和後序序列如下:

                               中序:G  L  D  H  B  E  I  A  C  J  F  K

                               後序:L  G  H  D  I   E  B  J  K  F  C  A

則可以唯一確定一棵二叉樹。

#include<iostream.h>

#include<string.h>

#include<stdlib.h>

#define MAX 20 /*預定義字元陣列的最大長度*/

typedef struct tnode /*該結構體型別為樹結點的型別*/

{

       char data;

       struct tnode *lchild;

       struct tnode *rchild;

} *bt;

void in_post_to_bt(char *in,char *post,int len,bt &T) /*由長度為len的中序序列in和後序序列post唯一確定一棵二叉樹T*/

{

       int k;

       if(len<=0)

       {

              T=NULL;

              return;

       }

       for(char *temp=in;temp<in len;temp ) /*在中序序列in中找到根節點所在的位置*/

              if(*(post len-1)==*temp)

              {

                     k=temp-in;  /*k為根結點在中序序列中的下標*/

                     T=(bt)malloc(sizeof(struct tnode));

                     T->data =*temp;

                     break;

              }

       in_post_to_bt(in,post,k,T->lchild ); /*建立左子樹*/

       in_post_to_bt(in k 1,post k,len-k-1,T->rchild ); /*建立右子樹*/

}

void in_visit(bt T)/*中序遍歷樹T*/

{

       if(T)

       {

              in_visit(T->lchild );

              cout<<T->data ;

              in_visit(T->rchild );

       }

}

void post_visit(bt T)/*後序遍歷樹*/

{

       if(T)

       {

              post_visit(T->lchild );

              post_visit(T->rchild );

              cout<<T->data ;

       }

}

main()

{

       char in[MAX 1],post[MAX 1];

       cout<<“輸入中序序列:”;

       cin>>in;

       cout<<“輸入後序序列:”;

       cin>>post;

       bt T;

       int len_in=strlen(in),len_post=strlen(post);

       if(len_in<=MAX&&len_post<=MAX)

              in_post_to_bt(in,post,len_in,T);

       cout<<endl<<“輸出中序序列:”;

       in_visit(T);

       cout<<endl<<“輸出後序序列:”;

       post_visit(T);

       cout<<endl;

}