|
实验目的： （1）掌握非线性数据结构–树结构，继续帮助学生建立数据结构加操作的程序设计方法。 （2）重点掌握树遍历操作，因为遍历操作是其他众多操作的基础，其中访问动作可是任何操作。 （3）了解应用树结构解决实际应用问题。 本次实验中，下列实验项目选做一。 实验内容： 以二叉链表存储结构，实现二叉树的建立、先序遍历、中序遍历、后序遍历、统计叶子个数等操作。 [基本要求及提示] （1）从键盘输入扩展的先序结点数据，建立二叉树。 （2）先序遍历，输出结点序列。 （3）中序遍历，输出结点序列。 （4）后序遍历，输出结点序列。 （5）统计叶子结点个数。 （6）要求程序通过一个主菜单进行控制，通过选择菜单项序号调用各功能函数。
#include
#include
typedef struct BiTNode//树的链式存储结构
{
char data;//结点数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T)//先序遍历的顺序建立二叉链表
{
char ch;
ch=getchar();//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
if(ch=='#') *T=NULL;//递归结束，建空树
else//递归创建二叉树
{
*T=(struct BiTNode*)malloc(sizeof(struct BiTNode));//生成根结点
(*T)->data=ch;//根结点数据域置为ch
CreateBiTree(&(*T)->lchild);//递归创建左子树
CreateBiTree(&(*T)->rchild);//递归创建右子树
}
}
void PreOrderTraverse(BiTree T)//先序打印结点
{
if(T!=NULL)//如果不是空树，执行如下操作
{
//打印结点，先序打印
printf("%3c",T->data);//先序遍历左子树
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);//先序遍历右子树
}
}
void middleOrderTraverse(BiTree T)//中序打印结点
{
if(T!=NULL)//如果不是空树，执行如下操作
{
//打印结点，中序打印
middleOrderTraverse(T->lchild);//中序遍历左子树
printf("%3c",T->data);
middleOrderTraverse(T->rchild);//中序遍历右子树
}
}
void lastOrderTraverse(BiTree T)//后序打印结点
{
if(T!=NULL)//如果不是空树，执行如下操作
{
//打印结点，后序打印
lastOrderTraverse(T->lchild);//后序遍历左子树
lastOrderTraverse(T->rchild);//后序遍历右子树
printf("%3c",T->data);
}
}
int LeafCount(BiTree T)
{
int x=0;
if(T==NULL)return ;
if((T->lchild==NULL)&&(T->rchild==NULL))
x++;
x+=LeafCount(T->lchild);//先序遍历左子树
x+=LeafCount(T->rchild);//先序遍历右子树}
return x;
}
int main()
{
BiTree T;//创建bitree类型的变量T
int order=1,x1;
puts("\t菜单");
puts("\t1输入先序结点数据，建立二叉树");
puts("\t2先序遍历，输出结点序列");
puts("\t3中序遍历，输出结点序列");
puts("\t4后序遍历，输出结点序列");
puts("\t5统计叶子结点个数");
puts("\t0结束");
while(order!=0)
{
printf("\n请输入指令\n");
scanf("%d",&order);
switch(order)
{
case 1:printf("请输入结点数据:");
getchar();
CreateBiTree(&T);break;
case 2:PreOrderTraverse(T);break;
case 3:middleOrderTraverse(T);break;
case 4:lastOrderTraverse(T);break;
case 5:x1=LeafCount(T);printf("叶子结点有%d个\n",x1);break;
}
}
}
|