#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
typedef struct Bitnode{
char data;
struct Bitnode *lchild,*rchild;
}Bitnode,*Bitree;
void creatBitree(Bitree *T)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
(*T)=NULL;
else
{
(*T)=(Bitnode*)malloc(sizeof(Bitnode));
(*T)->data=ch;
creatBitree(&(*T)->lchild);
creatBitree(&(*T)->rchild);
}
}
void xianxuBitree(Bitree T)
{
if(T)
{
printf("%c",T->data);
xianxuBitree(T->lchild);
xianxuBitree(T->rchild);
}
}
void zhongxuBitree(Bitree T)
{
if(T)
{
zhongxuBitree(T->lchild);
printf("%c",T->data);
zhongxuBitree(T->rchild);
}
}
void houxuBitree(Bitree T)
{
if(T)
{
houxuBitree(T->lchild);
houxuBitree(T->rchild);
printf("%c",T->data);
}
}
void dayin(Bitree T,int d) //按树状打印
{
if(!T)
return ;
dayin(T->rchild,d+1);
for(int i=0;i<d;i++)
printf(" ");
printf("%c\n",T->data);
dayin(T->lchild,d+1);
}
void yejiedian(Bitree T,int *count)
{
if(T)
{
if((!T->lchild)&&(!T->rchild))
(*count)++;
else
{
yejiedian(T->lchild,count);
yejiedian(T->rchild,count);
}
}
}
int shendu(Bitree T) //后序遍历求深度
{
int depthz,depthl,depthr;
if(!T)
depthz=0;
else
{
depthl=shendu(T->lchild);
depthr=shendu(T->rchild);
if(depthr>depthl)
depthz=depthr+1;
else
depthz=depthl+1;
}
return depthz;
}
int main()
{
Bitree T;
int s=0,d,w=0;
creatBitree(&T);
printf("先序遍历为：");
xianxuBitree(T);
printf("\n中序遍历：");
zhongxuBitree(T);
printf("\n后续遍历:");
houxuBitree(T);
printf("\n按树状打印\n");
dayin(T,w);
yejiedian(T,&s); //把地址传到函数里，那么*count代表地址里面的值，那么此时的count就是地址
printf("\n叶节点：%d",s);
d=shendu(T);
printf("\n深度%d",d);
return 0;
}