#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef char datatype;
//结构体
typedef struct node
{
datatype data;
struct node *lchild;
struct node *rchild;
}*Btree;
//创建结点
Btree creat()
{
Btree s=(Btree)malloc(sizeof(struct node));
if(s==NULL) return NULL;
s->data='\0';
s->lchild=s->rchild=NULL;
return s;
}
//创建树
Btree creat_tree()
{
datatype element;
printf("please input element:");
scanf(" %c",&element);
if(element=='#')
return NULL;
Btree tree=creat();
tree->data=element;
tree->lchild=creat_tree();
tree->rchild=creat_tree();
return tree;
}
//先序遍历
void first(Btree tree)
{
if(tree==NULL) return;
printf("%c",tree->data);
first(tree->lchild);
first(tree->rchild);
}
//中序遍历
void mid(Btree tree)
{
if(tree==NULL) return;
mid(tree->lchild);
printf("%c",tree->data);
mid(tree->rchild);
}
//后序遍历
void last(Btree tree)
{
if(tree==NULL) return;
last(tree->lchild);
last(tree->rchild);
printf("%c",tree->data);
}
//结点个数
void count(Btree tree,int *n0,int *n1,int *n2)
{
if(tree==NULL)
return;
if(tree->lchild ==NULL&&tree->rchild==NULL)
++*n0;
else if(tree->lchild&&tree->rchild)
++*n2;
else
++*n1;
count(tree->lchild,n0,n1,n2);
count(tree->rchild,n0,n1,n2);
}
//计算深度
int high(Btree tree)
{
if(tree==NULL)
return 0;
int left=1+high(tree->lchild);
int right=1+high(tree->rchild);
return left>right?left:right;
}
int main(int argc, const char *argv[])
{
Btree tree=creat_tree();
printf("first:");
first(tree);
puts("");
printf("mid:");
mid(tree);
puts("");
printf("last:");
last(tree);
puts("");
int n0=0,n1=0,n2=0;
count(tree,&n0,&n1,&n2);
printf("n0=%d n1=%d n2=%d n=%d\n",n0,n1,n2,n0+n1+n2);
int high_tree=high(tree);
printf("high_tree=%d\n",high_tree);
return 0;
}