由前序和中序构造一棵树 后续遍历

#include<stdio.h>
#include<malloc.h>

typedef struct Node
{
	char data;
	struct Node *lchild;
	struct Node *rchild;
}*BiTree,BitNode;

void InitBitTree(BiTree *T);//初始化一棵树
void CreateBiTree(BiTree *T,char *pre,char *in,int len);//由前序和中序构造一棵树
int Depth(BiTree T);//求一棵树的深度
void Travel(BiTree T);

void main()
{
	BiTree T;
	InitBitTree(&T);
	char a[50],b[50];
	int i,len=0,j;
	printf("Please input pre_order for a tree:\n ");
	gets(a);
	printf("Please input in_order for a tree:\n ");
	gets(b);
	for(i=0;i<50;i++)
	{
		if(a[i]!='\0')
			len++;
		else
			break;
	}
	CreateBiTree(&T,a,b,len);
	j=Depth(T);
	printf("这棵树的深度是：%d\n",j);
	Travel(T);//后续遍历一棵树
}
void InitBitTree(BiTree *T)//初始化一棵树
{
	*T=NULL;
}

void CreateBiTree(BiTree *T,char *pre,char *in,int len)//由前序和中序构造一棵树
{
	int k;
	char *temp;
	if(len<=0)
	{
		*T=NULL;
		return;
	}
	*T=(BitNode*)malloc(sizeof(BitNode));
	(*T)->data=*pre;
	for(temp=in;temp<in+len;temp++)
		if(*pre==*temp)
			break;
		k=temp-in;
		CreateBiTree(&((*T)->lchild),pre+1,in,k);  //左子树
		CreateBiTree(&((*T)->rchild),pre+1+k,temp+1,len-1-k);//右子树
}
int Depth(BiTree T)//求一棵树的深度

{
	int h,lh,rh;
	if(T==NULL)
		h=0;
	else
	{
		lh=Depth(T->lchild);
		rh=Depth(T->rchild);
		if(lh>=rh)
			h=lh+1;
		else
			h=rh+1;
	}
	return h;
}
void Travel(BiTree T) //后续遍历一棵树
{
	if(T) 
	{
		Travel(T->lchild); 
		Travel(T->rchild); 
		putchar(T->data); 
	}
	//printf("\n");
}

//  下面是先序建立一棵树

#define NULL 0
#include "stdio.h"
#include "stdlib.h"

//二叉链表结点定义
struct tree
{
   int data;
   struct tree *lchild;
   struct tree *rchild;
};

// 先序建立二叉树
struct tree *create(struct tree *BT,int k)
{
  struct tree *p;
  int x;
  p=(struct tree *)malloc(sizeof(struct tree)); 
  printf("输入结点的整数值（0表示空） : ");
  scanf("%d",&x);
  if(x!=0)
  {
     if(!(p=(struct tree *)malloc(sizeof(struct tree))))
      exit(0);
  //生成主根或子树根
     p->data=x; 
     p->lchild=NULL;
     p->rchild=NULL;
     if(k==0)
      BT=p;
     if(k==1)
       BT->lchild=p;
     if(k==2)
      BT->rchild=p;
     create(p,1);//建立左子树
     create(p,2);//建立右子树
  }
  return(BT);
}
// 先序遍历
int visit(struct tree *BT)
{
  if(BT!=NULL)
    {
      printf("%d ",BT->data);
      visit(BT->lchild);
      visit(BT->rchild);
    }
  return 0;
}

void main()
{
  struct tree *p;
  p=(struct tree *)malloc(sizeof(struct tree));
  p=create(p,0);
  visit(p);
  printf("\n");
}