#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
typedef char elemtype;
typedef struct tree //二叉树结构体
{
elemtype data;
struct tree *lchild;
struct tree *rchild;
}TREE;
TREE *createbitree() //递归建立二叉树{
char ch;
TREE *p;
ch=getchar();
if (ch=='#')
p=NULL;
else
{
p=(TREE *)malloc(sizeof(TREE));
p->data=ch;
p->lchild=createbitree();
p->rchild=createbitree();
}
return p;
}
void preorder(TREE *p) //前序遍历
{
if(p!=NULL)
{
printf("%c ",p->data);
preorder(p->lchild);
preorder(p->rchild);
}
}
void inorder(TREE *p) //中序遍历
{
if (p!=NULL)
{
inorder(p->lchild);
printf("%c ",p->data);
inorder(p->rchild);
}
}
void postorder(TREE *p) //后序遍历
{
if (p!=NULL)
{
postorder(p->lchild);
postorder(p->rchild);
printf("%c ",p->data);
}
}
void shu(TREE *p,int len) //数的形状{
if (p!=NULL)
{
shu(p->lchild,len+1);
for (int i=1;i<=4*len;i++)
{
printf(" ");
}
printf("%c",p->data);
printf("------\n");
shu(p->rchild,len+1);
}
}
int shendu(TREE *p) //计算深度
{
int l,r;
if (p==NULL)
{
return 0;
}
l=shendu(p->lchild)+1;
r=shendu(p->rchild)+1;
if (l>=r) //左右子树比较return l;
else
return r;
}
int dianshu(TREE *p) //计算结点数
{
int s;
if (p==NULL)
{
return 0;
}
s=dianshu(p->lchild)+dianshu(p->rchild)+1;
return s;
}
void jiemian() //操作界面
{
printf("请选择功能:\n");
printf("=========================\n");
printf("* 1.看看我建立的树\n");
printf("* 2.看看它的深度和叶子结点数\n");
printf("* 3.前、中、后序遍历\n");
printf("* 4.结束····\n");
printf("=========================\n");
printf("请选择：\n");
}
void main()
{
TREE *p;
int len=0,c,flag=1,i=0,s,a;
printf("实验3 二叉树的建立及其应用：\n");
printf("\n");
printf("请输入结点元素，输入#表示空（按前序输入）：\n");
p=createbitree();
while (flag) //循环
{
jiemian();
scanf("%d",&c);
switch (c)
{
case 1:
printf("数的形状：\n");
shu(p,len);
getch();
system("CLS");
break;
case 2:
printf("此树的深度：\n");
s=shendu(p);
printf("%d\n",s);
printf("\n");
printf("此树的结点数：\n");
a=dianshu(p);
printf("%d\n",a);
printf("\n");
printf("数的形状：\n");
shu(p,len);
getch();
system("CLS");
break;
case 3:
printf("前序遍历结果：\n");
printf("\n");
preorder(p);
printf("\n");
printf("\n");
printf("中序遍历结果：\n");
printf("\n");
inorder(p);
printf("\n");
printf("\n");
printf("后序遍历结果：\n");
printf("\n");
postorder(p);
printf("\n");
printf("\n");
getch();
system("CLS");
break;
default:
flag=0;
exit(0);
break;
}
}
}。