一、实验目的
- 掌握二叉树的链表存储结构。
- 熟练二叉树的遍历算法。
- 加深数据结构程序设计的理解
二、实验要求
有下图所示的二叉树,编写一个程序exp6-1.c,实现二叉树的各种基本运算和下面main函数中的每一步功能。
- 根据二叉树的括号表示法 A（B（D，E（G，H）），C（，F（K）））,创建该二叉树的链式存储，并输出该二叉树；
- 求该二叉树的高度；
- 求该二叉树的结点数；
- 求该二叉树的叶子结点数；
- 输出二叉树的先序遍历的序列；
- 输出二叉树的中序遍历的序列；
- 输出二叉树的后序遍历的序列；
- 输出二叉树的层序遍历的序列；
- 销毁该二叉树。
三、实验环境
Windows+DEV C++( 或者其他编译工具)
四、实验步骤及结果
1.类型声明
typedef char ElemType;
typedef struct node
{
ElemType data;//数据元素
struct node *lchild; //指向左孩子结点
struct node *rchild;//指向右孩子结点
} BTNode;
2.二叉树基本运算在链式存储结构上的实现
void CreateBTree(BTNode *&b,char *str)
{
BTNode *St[MaxSize],*p=NULL;// St数组作为顺序栈
int top=-1,k,j=0;//top为栈顶指针
char ch;
b=NULL;//初始时二叉链为空
ch=str[j];
while (ch!='\0')//遍历str中的每个字符
{
switch(ch)
{
case '(':top++;St[top]=p;k=1;break;//开始处理左孩子结点
case ')':top--;break;//栈顶结点的子树处理完毕
case ',':k=2;break;//开始处理右孩子结点
default:p=(BTNode *)malloc(sizeof(BTNode));//创建一个结点，由p指向它
p->data=ch;// 存放结点值
p->lchild=p->rchild=NULL;//左、右指针都设置为空
if (b==NULL)//若尚未建立根结点
b=p;//p所指结点作为根结点
else//已建立二叉树根结点
{
switch(k)
{
case 1:St[top]->lchild=p;break;//新建结点作为栈顶结点的左孩子
case 2:St[top]->rchild=p;break;//新建结点作为栈顶结点的右孩子
}
}
}
j++;//继续遍历str
ch=str[j];
}
}3. 程序exp6-1.c的设计，及完成实验要求中的功能
#include <iostream>
using namespace std;
#include <stdlib.h>
#include <string>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;//数据元素
struct node *lchild; //指向左孩子结点
struct node *rchild;//指向右孩子结点
} BTNode;
void CreateBTree(BTNode *&b,char *str)
{
BTNode *St[MaxSize],*p=NULL;// St数组作为顺序栈
int top=-1,k,j=0;//top为栈顶指针
char ch;
b=NULL;//初始时二叉链为空
ch=str[j];
while (ch!='\0')//遍历str中的每个字符
{
switch(ch)
{
case '(':top++;St[top]=p;k=1;break;//开始处理左孩子结点
case ')':top--;break;//栈顶结点的子树处理完毕
case ',':k=2;break;//开始处理右孩子结点
default:p=(BTNode *)malloc(sizeof(BTNode));//创建一个结点，由p指向它
p->data=ch;// 存放结点值
p->lchild=p->rchild=NULL;//左、右指针都设置为空
if (b==NULL)//若尚未建立根结点
b=p;//p所指结点作为根结点
else//已建立二叉树根结点
{
switch(k)
{
case 1:St[top]->lchild=p;break;//新建结点作为栈顶结点的左孩子
case 2:St[top]->rchild=p;break;//新建结点作为栈顶结点的右孩子
}
}
}
j++;//继续遍历str
ch=str[j];
}
}
void DestroyBTree(BTNode *&b)
{
if (b!=NULL)
{
DestroyBTree(b->lchild);
DestroyBTree(b->rchild);
free(b);
}
}
int BTHeight(BTNode *b)
{
int lchildh,rchildh;
if (b==NULL) return(0);//空树的高度为0
else
{
lchildh=BTHeight(b->lchild);//求左子树的高度为lchildh
rchildh=BTHeight(b->rchild);//求右子树的高度为rchildh
return (lchildh>rchildh)?(lchildh+1):(rchildh+1);
}
}
int NodeCount(BTNode *b)//结点数
{
int num1,num2;
if (b==NULL) return 0;
else
{
num1=NodeCount(b->lchild);
num2=NodeCount(b->rchild);
return (num1+num2+1);
}
}
int LeafCount(BTNode *b)//叶子结点数
{
int num1,num2;
if (b==NULL) return 0;
else if (b->lchild==NULL && b->rchild==NULL) return 1;
{
num1=LeafCount(b->lchild);
num2=LeafCount(b->rchild);
return (num1+num2);
}
}
void DispBTree(BTNode *b)//输出结点
{
if (b!=NULL)
{
printf("%c",b->data);
if (b->lchild!=NULL || b->rchild!=NULL)
{
printf("(");
DispBTree(b->lchild);//输出左子树中的节点数
if (b->rchild!=NULL)
printf(",");
DispBTree(b->rchild);//输出右子树中的节点数
printf(")");
}
}
}
void PreOrder(BTNode *b)//先序遍历递归算法
{
if (b!=NULL)
{
printf("%c",b->data);//访问根结点
PreOrder(b->lchild);//先序遍历左子树
PreOrder(b->rchild);//先序遍历右子树
}
}
void InOrder(BTNode *b)//中序遍历递归算法
{
if (b!=NULL)
{
InOrder(b->lchild);//中序遍历左子树
printf("%c",b->data);//访问根结点
InOrder(b->rchild);//中序遍历右子树
}
}
void PostOrder(BTNode *b)//后序遍历递归算法
{
if (b!=NULL)
{
PostOrder(b->lchild);//后序遍历左子树
PostOrder(b->rchild);//后序遍历右子树
printf("%c",b->data);//访问根结点
}
}
void LevelOrder(BTNode *b)//层序遍历算法
{
BTNode *p;
BTNode *qu[MaxSize];
int front,rear;
front=rear=0;
rear++;qu[rear]=b;
while (front!=rear)
{
front=(front+1)%MaxSize;
p=qu[front];
printf("%c",p->data);
if (p->lchild!=NULL)//有左孩子时将其进队
{
rear=(rear+1)%MaxSize;
qu[rear]=p->lchild;
}
if (p->rchild!=NULL)//有右孩子时将其进队
{
rear=(rear+1)%MaxSize;
qu[rear]=p->rchild;
}
}
}
int main()
{
BTNode *b;
CreateBTree(b,"A(B(D,E(G,H)),C(,F(K)))");
printf("二叉树b:");DispBTree(b);printf("\n");
printf("b的高度:%d\n",BTHeight(b));
printf("b的结点数:%d\n",NodeCount(b));
printf("b的叶子结点数:%d\n",LeafCount(b));
printf("b的先序遍历序列：");PreOrder(b);printf("\n");
printf("b的中序遍历序列：");InOrder(b);printf("\n");
printf("b的后序遍历序列：");PostOrder(b);printf("\n");
printf("b的层次遍历序列：");LevelOrder(b);printf("\n");
DestroyBTree(b);
}4.实验结果截图
如需源文件，请私信作者，无偿