学步园

#include<stdio.h>
#include<malloc.h>
#define ElemType char

//建立树的数据结构类型
typedef struct Tree
{
 ElemType data;
 struct Tree *lchild,*rchild;
}Tree,*Stree;

//树的建立
void create(Stree &t)//注意这里必须用引用
{
 ElemType da;
 scanf("%c",&da);
 if(da=='*')
  t=NULL;//return NULL;
 else
 {
  //p=(Stree)malloc(sizeof(Tree));
  t=(Stree)malloc(sizeof(Tree));
  t->data=da;
  create(t->lchild);
  create(t->rchild);
 }
}

//树的先序遍历
void preorder(Stree t)
{
 if(t)
 {
  printf("%c",t->data);
  preorder(t->lchild);
  preorder(t->rchild);
 }
}

//树的中序遍历
void midorder(Stree t)
{
 if(t)
 {
  midorder(t->lchild);
  printf("%c",t->data);
  midorder(t->rchild);
 }
}

//树的后序遍历
void postorder(Stree t)
{
 if(t)
 {
  postorder(t->lchild);
  postorder(t->rchild);
  printf("%c",t->data);
 }
}

//求树的叶子结点
void countleaf(Stree t,int &count)
{
 if(t)
 {
  if(t->lchild==NULL&&t->rchild==NULL)
  {
   printf("叶子结点：%c/n",t->data);
   count++;
  }
  else
  {
   countleaf(t->lchild,count);
   countleaf(t->rchild,count);
  }
 }
}

//求树的深度
int depth(Stree t)
{
 int d,ld,rd;
 if(t==NULL)
  d=0;
 else
 {
  ld=depth(t->lchild);
  rd=depth(t->rchild);
  d=ld>rd?ld:rd;
  d++;
 }
 return d;
}

//主函数部分
void main()
{
 int count,dep;
 Stree t=NULL;
 printf("请输入树的序列:/n");
 //测试数据：abc**de*g**f***
 create(t);
 printf("先序遍历的结果:/n");
 preorder(t);
 printf("/n");
 printf("中序遍历的结果:/n");
 midorder(t);
 printf("/n");
 printf("后序遍历的结果:/n");
 postorder(t);
 printf("/n");
 count=0;
 countleaf(t,count);
 printf("树的叶子结点的个数是：%d/n",count);
 dep=depth(t);
 printf("树的深度是：%d/n",dep);
}
/*
请输入树的序列:
abc**de*g**f***
先序遍历的结果:
abcdegf
中序遍历的结果:
cbegdfa
后序遍历的结果:
cgefdba
叶子结点：c
叶子结点：g
叶子结点：f
树的叶子结点的个数是：3
树的深度是：5
Press any key to continue
*/