数据结构实验：二叉树操作

Luz5年前 (2019-12-02)实验4164

实验题目：二叉树操作
需求分析：
本演示程序在TC2.0环境下编写调试，完成二叉链表初始化，先根遍历，中根遍历，后根遍历二叉树，按某种形式输出二叉树，求二叉树高度，求二叉树叶节点个数，交换二叉树左右子树，借助队列实现层次遍历等操作。
首先要根据键盘输入的数据建立一个二叉链表，其次根据屏幕的菜单选择，可以进行二叉树的遍历输出等操作，最后在屏幕菜单中选择0，即可结束程序的运行。

输入节点序号，节点数据，建立二叉树
建立二叉树方法1依次输入数据 1,5 2,9 3,7 4,8 5,6 0,0
建立二叉树方法2依次输入数据 abd#g###ce#h##f##
分别执行先根，中根，后根，层次遍历
分别计算二叉树高度，叶子节点
交换二叉树的左右子树
程序所能达到的功能。完成二叉链表的生成、遍历、输出、求高度、求叶节点个数、交换左右子树，层次遍历的操作。
测试数据。

概要设计

主函数main()
建立二叉树方法1 creat_bt1()
建立二叉树方法2 creat_bt2()
先根遍历二叉树 preorder()
中根遍历二叉树 inorder()
后根遍历二叉树 postorder()
层次遍历二叉树 levorder()
求二叉树高度 treedepth()
求二叉树叶子节点个数 leafcount()
求二叉树叶子节点 paintleaf()
交换二叉树左右子树 exchange()
逆时针90°输出二叉树 prtbtree()
建立队列函数 enqueue()
删除队列函数 delqueue()
为了实现上述程序功能，需要定义循环顺序队列的数据结构。
本程序包含14个函数

详细设计
#include<stdio.h>
#include<stdlib.h>
#define M 100
typedef char Etype;
typedef struct BiTNode
{
Etype data;
struct BiTNode *lch,*rch;
}BiTNode,*BiTree;
BiTree que[M];
int front=0,rear=0;
BiTNode *creat_bt1();
BiTNode *creat_bt2();
void preorder(BiTNode *p);
void inorder(BiTNode *p);
void postorder(BiTNode *p);
void enqueue(BiTree);
BiTree delqueue( );
void levorder(BiTree);
int treedepth(BiTree);
void prtbtree(BiTree,int);
void exchange(BiTree);
int leafcount(BiTree);
void paintleaf(BiTree);
BiTNode *t;
int count=0;
int main()
{
char ch;
int k;
do
{
    printf("\n\n\n");
    printf("\n=========主菜单==========");
    printf("\n\n 1.建立二叉树方法1");
    printf("\n\n 2.建立二叉树方法2");
    printf("\n\n 3.先序递归遍历二叉树");
    printf("\n\n 4.中序递归遍历二叉树");
    printf("\n\n 5.后序递归遍历二叉树");
    printf("\n\n 6.层次遍历二叉树");
    printf("\n\n 7.计算二叉树的高度");
    printf("\n\n 8.计算二叉树中叶结点个数");
    printf("\n\n 9.交换二叉树的左右子树");
    printf("\n\n 10.打印二叉树");
    printf("\n\n 0.结束程序运行");
    printf("\n============================");
    printf("\n 请输入您的选择(0,1,2,3,4,5,6,7,8,9,10)");
    scanf("%d",&k);
switch(k)
{
case 1:t=creat_bt1();break;
case 2:printf("\n请输入二叉树各结点的值：");fflush(stdin);
        t=creat_bt2();break;
case 3:if(t)
{
    printf("先序遍历二叉树:");
    preorder(t);
    printf("\n");
}
    else printf("二叉树为空！\n");
    break;
case 4:if(t)
{
printf("中序遍历二叉树:");
inorder(t);
printf("\n");
}
else printf("二叉树为空！\n");
break;
case 5:if(t)
{
printf("后序遍历二叉树：");
postorder(t);
printf("\n");
}
else printf("二叉树为空！\n");
break;
case 6:if(t)
{
printf("层次遍历二叉树：");
levorder(t);
printf("\n");
}
else printf("二叉树为空！\n");
break;
case 7:if(t)
{
printf("二叉树的高度为：%d",treedepth(t));
printf("\n");
}
else printf("二叉树为空！\n");
break;
case 8:if(t)
{
printf("二叉树的叶子结点数为：%d\n",leafcount(t));
printf("二叉树的叶子结点数为：");
paintleaf(t);
printf("\n");
}
else printf("二叉树为空！\n");
break;
case 9:if(t)
{
printf("交换二叉树的左右子数：\n");
exchange(t);
prtbtree(t,0);
printf("\n");
}
else printf("二叉树为空！\n");
break;
case 10:if(t)
{
printf("逆时针旋转90度输出的二叉树：\n");
prtbtree(t,0);
printf("\n");
}
else printf("二叉树为空！\n");
break;
case 0:exit(0);
}
}while(k>=1&&k<=10);
printf("\n再见！按回车键，返回...\n");
ch=getchar();
}
BiTNode*creat_bt1()
{
BiTNode *t,*p,*v[20];int i,j;Etype e;
printf("\n请输入二叉树各结点的编号和对应的值（如1，a）:");
scanf("%d,%c",&i,&e);
while(i!=0&&e!='#')
{
p=(BiTNode * )malloc(sizeof(BiTNode));
p->data=e;p->lch=NULL;p->rch=NULL;
v[i]=p;
if(i==1)t=p;
else
{
j=i/2;
if(i%2==0)
v[j]->lch=p;
else
v[j]->rch=p;
}
printf("\n请继续输入二叉树各结点的编号和对应的值：");
scanf("%d,%c",&i,&e);
}
return(t);
}
BiTNode * creat_bt2()
{
BiTNode *t;Etype e;
scanf("%c",&e);
if(e=='#')t=NULL;
else
{
t=(BiTNode * )malloc(sizeof(BiTNode));
t->data=e;
t->lch=creat_bt2();
t->rch=creat_bt2();
}
return(t);
}
void preorder(BiTNode *p)
{
if(p)
{
printf("%3c",p->data);
preorder(p->lch);
preorder(p->rch);
}
}
void inorder(BiTNode *p)
{
if(p)
{
inorder(p->lch);
printf("%3c",p->data);
inorder(p->rch);
}
}
void postorder(BiTNode *p)
{
if(p)
{
postorder(p->lch);
postorder(p->rch);
printf("%3c",p->data);
}
}
void enqueue(BiTree T)
{
if(front!=(rear+1)%M)
{
rear=(rear+1)%M;
que[rear]=T;
}
}
BiTree delqueue()
{
if(front==rear)return NULL;
front=(front+1)%M;
return(que[front]);
}
void levorder(BiTree T)
{BiTree p;
if(T)
{
enqueue(T);
while(front!=rear)
{
p=delqueue( );
printf("%3c",p->data);
if(p->lch!=NULL)enqueue(p->lch);
if(p->rch!=NULL)enqueue(p->rch);
}
}
}
int treedepth(BiTree bt)
{
int hl,hr,max;
if(bt!=NULL)
{
hl=treedepth(bt->lch);
hr=treedepth(bt->rch);
max=(hl>hr)?hl:hr;
return(max+1);
}
else return(0);
}
void prtbtree(BiTree bt,int level)
{
int j;
if(bt)
{
prtbtree(bt->rch,level+1);
for(j=0;j<=6*level;j++)
printf(" ");
printf("%c\n",bt->data);
prtbtree(bt->lch,level+1);
}
}
void exchange(BiTree bt)
{
BiTree p;
if(bt)
{
p=bt->lch;bt->lch=bt->rch;bt->rch=p;
exchange(bt->lch);
exchange(bt->rch);
}
}
int leafcount(BiTree bt)
{
if(bt!=NULL)
{
leafcount(bt->lch);
leafcount(bt->rch);
if((bt->lch==NULL)&&(bt->rch==NULL))
count++;
}
return(count);
}
void paintleaf(BiTree bt)
{
if(bt!=NULL)
{
if(bt->lch==NULL&&bt->rch==NULL)
printf("%3c",bt->data);
paintleaf(bt->lch);
paintleaf(bt->rch);
}
}
调试分析

编译未发现错误

使用说明
程序名为二叉树luz.exe,运行环境为MS-DOS。程序执行后显示：
在"请输入你的选择（0,1,2,3,4,5,6,7,8,9,10）"后输入数字选择执行不同的功能。要求首先输入1或2建立二叉树，才可以进行其他的操作。
选择0：退出程序
选择1：显示"请输入二叉树各节点的编号和对应的值(如1,a):"
选择2：显示"请输入各节点的值。
选择3：输出先序递归遍历的二叉树
选择4：输出中序递归遍历的二叉树
选择5：输出后序递归遍历的二叉树
选择6：输出层次遍历的二叉树
选择7：输出二叉树的高度
选择8:输出二叉树中叶节点的个数和节点数据
选择9:交换二叉树的左右子树,并打印二叉树
选择10:打印二叉树
测试结果