#include <stdio.h>
#include <stdlib.h>
#include <string.h>
const int N = 100+5;
typedef struct node{
char data;
struct node *lchild,*rchild;
}BNode,*BTree;
void preOrder(BTree T);
void inOrder(BTree T);
void postOrder(BTree T);
BTree createTreePreIn(char *pre,char *in,int len);
BTree createTreePostIn(char *post,char *in,int len);
int getHeight(BTree T);
int getLeafCnt(BTree T);
int getNodeCnt(BTree T);
int main(){
freopen("btree1.in","r",stdin);
char pre[N],in[N];
while(~scanf("%s%s",pre,in)){
int n = strlen(pre);
BTree T = createTreePreIn(pre,in,n);
printf("\n从中还原的二叉树:")
printf("\n前序遍历:");
preOrder(T);
printf("\n中序遍历:");
inOrder(T);
printf("\n后序遍历:");
postOrder(T);
printf("\n二叉树的高度:%d",getHeight(T));
printf("\n二叉树的叶子数:%d",getLeafCnt(T));
printf("\n二叉树的结点数:%d",getNodeCnt(T));
printf("\n\n");
}
return 0;
}
BTree createTreePreIn(char *pre,char *in,int len)
{
if(len == 0)
return NULL;
BTree T = (BTree)malloc(sizeof(BNode));
T->data = pre[0];
int n = -1;
for(int i = 0;i < len;i++){
if(in[i] == pre[0])
n = i;
}
T->lchild = createTreePreIn(pre+1,in,n);
T->rchild = createTreePreIn(pre+1+n,in+1+n,len-1-n);
return T;
}
BTree createTreePostIn(char *post,char *in,int len)
{
if(len == 0)
return NULL;
BTree T = (BTree)malloc(sizeof(BNode));
T->data = post[len-1];
int n = -1;
for(int i = 0;i < len;i++){
if(in[i] == post[len-1])
n = i;
}
T->lchild = createTreePostIn(post,in,n);
T->rchild = createTreePostIn(post+n+1,in+n+1,len-1-n);
return T;
}
int getHeight(BNode *p)
{
if(p == NULL)
return 0;
int dl = getHeight(p->lchild);
int dr = getHeight(p->rchild);
return 1 + (dl > dr ? dl:dr);
}
void getLeafCnt(BNode *p,int &m)
{
if(p != NULL)
{
if(p->lchild == NULL && p->rchild == NULL)
m++;
getLeafCnt(p->lchild,m);
getLeafCnt(p->rchild,m);
}
}