编辑代码

#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);
    }
}