下面我写的代码:
/* Note:Your choice is C IDE */
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct lbtree
{
char data;
struct lbtree *lchild,*rchild;
};
struct lbtree *createbtree();
void preorder(struct lbtree *root);
void inorder(struct lbtree *root);
void postorder(struct lbtree *root);
treedepth(struct lbtree *root);
numberofleaf(struct lbtree *root);
main()
{
struct lbtree *root;
int i;
printf("create a tree\n");
printf("please input nodes of tree\n");
root=NULL;
root=createbtree();
if(root==NULL)printf("This is an empty tree!\n");
else
{
printf("\n");
printf("1.The preorder traverse \n");
printf("2.The inorder traverse \n");
printf("3.The postorder traverse \n");
printf(" Please choose a kind of order\n");
scanf("%d",&i);
switch(i)
{
case 1:preorder(root);break;
case 2:inorder(root);break;
case 3:postorder(root);break;
default:printf("error!\n");
}
}
printf("\n The depth of the btree is %d",treedepth(root));
printf("\n The leafnumber of the btree is %d",numberofleaf(root));
}
struct lbtree *createbtree()
{
char ch,t;
struct lbtree *root;
printf("please input the data,'$' is the end.\n");
scanf("%c",&ch);
scanf("%c",&t);
if(ch=='$')
return(NULL);
else
{
root=(struct lbtree *)malloc(sizeof(struct lbtree));
root->data=ch;
root->lchild=createbtree();
root->rchild=createbtree();
return(root);
}
printf("ok!");
}
void preorder(struct lbtree *root)
{
if(root)
{
printf(" %c",root->data);
preorder(root->lchild);
preorder(root->rchild);
}
}
void inorder(struct lbtree *root)
{
if(root){inorder(root->lchild);
printf(" %c",root->data);
inorder(root->rchild);
}
}
void postorder(struct lbtree *root)
{
if(root)
{
postorder(root->lchild);
postorder(root->rchild);
printf(" %c",root->data);
}
}
treedepth(struct lbtree *root)
{
int depth,dl,dr;
if(!root)depth=0;
else
{
dl=treedepth(root->lchild);
dr=treedepth(root->rchild);
if(dl>dr)depth=dl+1;
else depth=dr+1;
}
return(depth);
}
numberofleaf(struct lbtree *root)
{
int num=0,num1,num2;
if(root)
{
if((root->lchild==NULL)&&(root->rchild==NULL))num=1;
else
{ num1=numberofleaf(root->lchild);
num2=numberofleaf(root->rchild);
num=num1+num2;
}
}
return(num);
}
运行结果如图: