数据结构-二叉树.doc

常熟理工学院

《数据结构与算法》实验指导与报告书

_2017-2018_____学年 第__1__ 学期

专 业： 物联网工程
实验名称： 二叉树
实验地点： N6-210
指导教师： 聂盼红

计算机科学与工程学院
2017
实验六 二叉树
【实验目的】
1、掌握二叉树的基本存储表示。
2、掌握二叉树的遍历操作实现方法（递归和非递归方法）。
3、理解并实现二叉树的其他基本操作。
4、掌握二叉树的重要应用---哈夫曼编码的实现。
【实验学时】
4-6学时
【实验预习】
回答以下问题：
1、二叉树的二叉链表存储表示。
/*---二叉树的二叉链表存储表示---*/
typedef struct BTNode
{
char data ; /*结点数据*/
struct BTNode *lchild; /*左孩子指针*/
struct BTNode *rchild ; /*右孩子指针*/
}*BiTree;
2、二叉树的三种基本遍历方式。
/*先序遍历二叉树，补充递归算法*/
void PreOrder(BiTree p)
{
if(p!=NULL);
{
printf("%c",p->data); //访问根节点
PreOrder(p->lchild); //先序遍历左子数
PreOrder(p->rchild); //先序遍历右子数
}
}/*PreOrder*/

/*中序遍历二叉树，补充递归算法*/
void InOrder(BiTree p)
{
if(p!=NULL);
{
InOrder(p->lchild); //中序遍历左子数
printf("%c",p->data); //访问根节点
InOrder(p->rchild); //中序遍历右子数
}
}/*InOrder*/

/*后序遍历二叉树，补充递归算法*/
void PostOrder(BiTree p)
{
if(p!=NULL);
{
PostOrder(p->lchild); //后序遍历左子数
PostOrder(p->rchild); //后序遍历右子数
printf("%c",p->data); //访问根节点
}
}/*PostOrder*/

3、解释哈夫曼树和带权路径长度WPL。
哈夫曼树，是指权值为W1、W2、….Wn的n个叶节点所构成的二叉树中带权路径长度最小的二叉树。
从树根结点到到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度，通常记作：WPL=Σ（n，i=1）WiLi
【实验内容和要求】
1、 编写程序exp6_1.c，实现二叉树的链式存储及基本操作。
以下图所示的二叉树实现二叉树的二叉链表存储及基本操作，回答下列问题，补充完整程序，并调试运行验证结果。

（1）按照先序序列建立该二叉树。
读入的字符序列应为：A，B，C，*，*，D，E，*，G，*，*，F，*，*，* (*表示空指针)。
（2）该二叉树的三种遍历序列：
先序序列：A,B,C,D,E,G,F;
中序序列：C,B,E,G,D,F,A;
后序序列：C,G,E,F,D,B,A;
（3）按层次遍历该二叉树，得到的序列为：A,B,C,D,E,F,G
（4）该二叉树的深度为 5 。
（5）该二叉树的叶子结点数为：______3_____。
A
（6）交换该二叉树所有结点的左右次序得到的新二叉树为：（画出新二叉树的图）

B

C
D

E
F

G

（7）新二叉树的三种遍历序列分别为：
先序序列：A,B,D,C,F,G,E;
中序序列：D,B,F,G,C,E,A;
后序序列：D,G,F,E,C,B,A;

exp6_1.c参考程序如下：
#include<stdio.h>
#include<malloc.h>
#define MAX 20
/*---二叉树的二叉链表存储表示---*/
typedef struct BTNode
{
char data; /*结点数据*/
struct BTNode *lchild; /*左孩子指针*/
struct BTNode *rchild ; /*右孩子指针*/
} * BiTree;

/*---非递归遍历辅助队列---*/
typedef struct SqQueue
{
BiTree data[MAX];
int front,rear;
} SqQueue;

void createBiTree(BiTree *t); /*先序遍历创建二叉树*/
void PreOrder(BiTree p); /*先序遍历二叉树*/
void InOrder(BiTree p); /*中序遍历二叉树*/
void PostOrder(BiTree p); /*后序遍历二叉树*/
void RPreorder(BiTree p); /*先序遍历的非递归算法*/
void RInorder(BiTree p); /*中序遍历的非递归算法*/
void RPostorder(BiTree p); /*后序遍历的非递归算法*/
int depth(BiTree t); /*求二叉树的深度算法*/
BiTree gettreenode(char x,BiTree lptr,BiTree rptr);/*后序复制二叉树-建立结点*/
BiTree copytree(BiTree t); /*以后序遍历的方式复制二叉树*/
BiTree swap(BiTree b); /*交换二叉树的结点的左右孩子*/
void ccOrder(BiTree t); /*利用循环队列实现层次遍历*/
int Leaves(BiTree t); /*统计二叉树叶子结点（递归）*/
void release(BiTree t); /*释放二叉树*/

/*先序遍历创建二叉树*/
void createBiTree(BiTree * t)
{
char s;
BiTree q;
printf("\nplease input data:");
s=getchar();
getchar(); /*扔掉存在键盘缓冲区的输入结束回车符*/
if(s=='#') /*子树为空则返回*/
{
* t =NULL;
return;
}
else

{
q=(BiTree)malloc(sizeof(struct BTNode));
if(q==NULL)
{
printf("Memory alloc failure!");
exit(0);
}
q->data=s;
*t=q;
createBiTree(&q->lchild);/*递归建立左子树*/
createBiTree(&q->rchild);/*递归建立右子树*/
}

}/*createBiTree*/

/*先序遍历二叉树，补充递归算法*/
void PreOrder(BiTree p)
{
if(p!=NULL)
{
printf("%c",p->data); //访问根节点
PreOrder(p->lchild); //先序遍历左子数
PreOrder(p->rchild); //先序遍历右子数
}
}/*PreOrder*/

/*中序遍历二叉树，补充递归算法*/
void InOrder(BiTree p)
{
if(p!=NULL)
{
InOrder(p->lchild); //中序遍历左子数
printf("%c",p->data); //访问根节点
InOrder(p->rchild); //中序遍历右子数
}
}/*InOrder*/

/*后序遍历二叉树，补充递归算法*/
void PostOrder(BiTree p)
{
if(p!=NULL)
{
PostOrder(p->lchild); //后序遍历左子数
PostOrder(p->rchild); //后序遍历右子数
printf("%c",p->data); //访问根节点
}
}/*PostOrder*/

/*先序遍历的非递归算法*/
void RPreorder(BiTree p)
{
BiTree stack[MAX],q;
int top=0,i;
for(i=0; i<MAX; i++)
stack[i]=NULL; /*初始化栈*/
q=p;
while(q!=NULL)
{
printf("%c",q->data);
if(q->rchild!=NULL)
stack[top++]=q->rchild; /*右指针进栈*/
if(q->lchild!=NULL)
q=q->lchild; /*顺着左指针继续向下*/
else
if(top>0)
q=stack[--top]; /*左子树访问完，出栈继续访问右子树结点*/
else
q=NULL;
}
}/*RPreorder*/

/*中序遍历的非递归算法*/
void RInorder(BiTree p)
{
BiTree stack[MAX],q; //定义节点栈和搜索指针
int top=0;
q=p;
do
{
while(q)//左链所有节点入栈
{
stack[top++]=q;
q=q->lchild;
}
if(top>0)
{
q=stack[--top];
printf("%c",q->data); //访问根
q=q->rchild;
}
}while(q||top!=0);

}/*RInorder*/

/*后序遍历的非递归算法*/
void RPostorder(BiTree p)
{
BiTree stack[MAX],q;
int i,top=0,flag[MAX];
for(i=0; i<MAX; i++) /*初始化栈*/
{
stack[i]=NULL;
flag[i]=0;
}
q=p;
while(q!=NULL||top!=0)
{
if(q!=NULL) /*当前结点进栈，先遍历其左子树*/
{
stack[top]=q;
flag[top]=0;
top++;
q=q->lchild;
}
else
{
while(top)
{
if(flag[top-1]==0) /*遍历结点的右子树*/
{
q=stack[top-1];
q=q->rchild;
flag[top-1]=1;
break;
}
else
{
q=stack[--top];
printf("%c",q->data); /*遍历结点*/
}
}
}
if(top==0) break;
}
}/*RPostorder*/

/*求二叉树的深度算法，补充递归算法*/
int depth(BiTree t)
{ int lc,rc;
if(t==NULL)
return 0; //若为空树，则返回零
else
{
lc=depth(t->lchild); //递归求t的左子树深度
rc=depth(t->rchild);//递归求t的右子树深度
if(lc>rc)
return(lc+1);
else
return(rc+1);
}

}/*depth*/

/*建立结点*/
BiTree gettreenode(char x,BiTree lptr,BiTree rptr)
{
BiTree t;
t=(BiTree)malloc(sizeof(struct BTNode));
t-> data = x;
t->lchild = lptr;
t->rchild = rptr;
return(t);
}/*gettreenode*/

/*以后序遍历的方式递归复制二叉树*/
BiTree copytree(BiTree t)
{
BiTree newlptr,newrptr,newnode;
if(t==NULL)
return NULL;
if(t->lchild!=NULL)
newlptr = copytree(t->lchild);
else newlptr = NULL;
if(t->rchild!=NULL)
newrptr = copytree(t->rchild);
else newrptr = NULL;
newnode = gettreenode(t->data, newlptr, newrptr);
return(newnode);
}/*copytree*/

/*交换二叉树的结点的左右孩子*/
BiTree swap(BiTree b)
{
BiTree t,t1,t2;
if(b==NULL)
t=NULL;
else
{
t=(BiTree)malloc(sizeof(struct BTNode));
t->data=b->data;
t1=swap(b->lchild); /*递归交换左子树上的结点*/
t2=swap(b->rchild); /*递归交换右子树上的结点*/
t->lchild=t2; /*交换根t的左右子树*/
t->rchild=t1;
}
return(t);
}/*swap*/

/*利用循环队列实现层次遍历*/
void ccOrder(BiTree t)
{
BiTree p;
SqQueue qlist,*q; //利用循环队列，实现层次遍历
q=&qlist;
q->rear=0;
q->front=0; //初始化队列
p=t;
if(p!=NULL)
{
printf("%c",p->data); //访问根节点
q->data[q->rear]=p; //根节点入队
q->rear=(q->rear+1)%MAX; //修改队尾指针
while(q->front!=q->rear)
{
p=q->data[q->front]; //出队操作
q->front=(q->front+1)%MAX;
if(p->lchild!=NULL) //访问出队节点的左孩子，并且入队
{
printf("%c",p->lchild->data);
q->data[q->rear]=p->lchild;
q->rear=(q->rear+1)%MAX;
}
if(p->rchild!=NULL) //访问出队节点的右孩子，并且入队
{
printf("%c",p->rchild->data);
q->data[q->rear]=p->rchild;
q->rear=(q->rear+1)%MAX;
}
}
}
}/*ccOrder*/

/*统计二叉树叶子结点，补充递归算法*/
int Leaves(BiTree t)
{
if(t==NULL)
return 0;
if(t->lchild==NULL&&t->rchild==NULL)
return 1;
return (Leaves(t->lchild)+Leaves(t->rchild)); //左子数叶子节点加上右子数叶子结点数

}/*Leaves*/

/*释放二叉树*/
void release(BiTree t)
{
if(t!=NULL)
{
release(t->lchild);
release(t->rchild);
free(t);
}
}/*release*/

int main()
{
BiTree t=NULL,copyt=NULL;
int select;
do
{
printf("\n***************MENU******************\n");
printf(" 1. 按先序序列建立二叉树\n");
printf(" 2. 遍历二叉树（三种递归方法）\n");
printf(" 3. 遍历二叉树（三种非递归方法）\n");
printf(" 4. 层次遍历二叉树\n");
printf(" 5. 输出二叉树的深度\n");
printf(" 6. 统计二叉树的叶子结点数（递归）\n");
printf(" 7. 后序遍历方式复制一棵二叉树\n");
printf(" 8. 交换二叉树所有结点的左右孩子\n");
printf(" 0. EXIT");
printf("\n***************MENU******************\n");
printf("\ninput choice:");
scanf("%d",&select);
getchar();
switch(select)
{
case 1:
printf("\n1-按先序序列建立二叉树:\n");
printf("请依次输入结点序列：\n");
// BiTree gettreenode(x,&lptr,&rptr);
createBiTree(&t);
if(t!=NULL)
printf("二叉树创建成功！\n");
else
printf("二叉树未创建成功！\n");
break;
case 2:
printf("\n2-遍历二叉树（三种递归方法）:\n");
printf("\n先序遍历序列:");
PreOrder(t);
printf("\n中序遍历序列:");
InOrder(t);
printf("\n后序遍历序列:");
PostOrder(t);
printf("\n");
break;
case 3:
printf("\n3-遍历二叉树（三种非递归方法）:\n");
printf("\n先序遍历的非递归:");
RPreorder(t);
printf("\n中序遍历的非递归:");
RInorder(t);
printf("\n后序遍历的非递归:");
RPostorder(t);
printf("\n");
break;
case 4:
printf("\n4-层次遍历二叉树:\n");
printf("\n按层次遍历:");
ccOrder(t);
printf("\n");
break;
case 5:
printf("\n5-输出二叉树的深度:\n");
printf("\n二叉树的深度:%d",depth(t));
printf("\n");
break;
case 6:
printf("\n6-统计二叉树的叶子结点数（递归）:\n");
printf("\n叶子结点数为：%d",Leaves(t));
printf("\n");
break;
case 7:
printf("\n7-后序遍历方式复制一棵二叉树:\n");
copyt=copytree(t);
if(copyt!=NULL)
{
printf("\n先序递归遍历复制的二叉树:");
PreOrder(copyt);
}
else
printf("\n复制失败！");
printf("\n");
break;
case 8:
printf("\n8-交换二叉树所有结点的左右孩子:\n");
printf("\n先序递归遍历交换后的二叉树:");
PreOrder(swap(t)); /*如需输出中序和后序遍历的结果，增加调用*/
printf("\n");
break;
case 0:
release(t); /*释放二叉树*/
break;
default:
break;
}
}
while(select);
return 0;
}
exp6_1.c实验结果：
(1) 按照先序序列建立二叉树：

（2）该二叉树的三种递归遍历序列为：

（3）遍历二叉树（三种非递归方法）：

（4）层次遍历二叉树：

（5）输出二叉树的深度

（6）统计二叉树的叶子结点数（递归）

（7）后序遍历方式复制一棵二叉树

（8）交换二叉树所有结点的左右孩子

2、 编写程序exp6_2.c，实现哈夫曼树的建立和哈夫曼编码。
若有一组字符序列{a,c,e,i,s,t,w}，对应的出现频率为{10,1,15,12,3,4,13}。以此序列创建哈夫曼树和哈夫曼编码。回答下列问题，补充完整程序，并调试运行验证结果。
（1） 构造该序列的哈夫曼树，画出哈夫曼树的形态。（以结点值左小右大的原则）

eT658
t28
T425
i12
T533
e15
T318
w13
s 3

c1
t4
T14
a 10

（2） 写出对应的哈夫曼编码。
a的编码为111， c的编码为11000，e的编码为10，i的编码为00，
s的编码为11001，t的编码为1101，w的编码为01

（3） 计算编码的WPL。
WPL=3*10+5*1+2*15+2*12+5*3+4*4+2*13=146
exp6_2.c程序代码参考如下：
#include<stdio.h>
#define MAXVALUE 10000 /*定义最大权值*/
#define MAXLEAF 30 /*定义哈夫曼树中叶子结点个数*/
#define MAXNODE MAXLEAF*2-1
#define MAXBIT 10 /*定义哈夫曼编码的最大长度*/

typedef struct /*哈夫曼编码结构*/
{
int bit[MAXBIT];
int start;
}
HCodeType;

typedef struct /*哈夫曼树结点结构*/
{
char data;
int weight;
int parent;
int lchild;
int rchild;
}
HNodeType;

void HuffmanTree(HNodeType HuffNode[],int *hn);
void HuffmanCode(HNodeType HuffNode[],HCodeType HuffCode[],int n);
void HuffmanTree(HNodeType HuffNode[],int *hn)/*哈夫曼树的构造算法*/
{
int i,j,m1,m2,x1,x2,n;
printf("n:");
scanf("%d",&n);
getchar(); /*输入叶子结点个数*/
for (i=0; i<2*n-1; i++) /*数组HuffNode[ ]初始化*/
{
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;

}
printf("HuffNode:\n");
for (i=0; i<n; i++)
{
scanf("%c,%d",&HuffNode[i].data,&HuffNode[i].weight); /*输入n个叶子结点的权值*/
getchar();
}
for (i=0; i<n-1; i++) /*构造哈夫曼树*/
{
m1=m2=MAXVALUE;
x1=x2=0;
for (j=0; j<n+i; j++)
{
if (HuffNode[j].weight<m1 && HuffNode[j].parent==-1)
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if (HuffNode[j].weight<m2 && HuffNode[j].parent==-1)
{
m2=HuffNode[j].weight;
x2=j;
}
}
/*将找出的两棵子树合并为一棵子树*/
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
}
*hn=n;
}

void HuffmanCode(HNodeType HuffNode[],HCodeType HuffCode[],int n) /*生成哈夫曼编码*/
{
HCodeType cd;
int i,j,c,p;
for(i=0; i<n; i++) /*求每个叶子结点的哈夫曼编码*/
{
cd.start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1) /*由叶结点向上直到树根*/
{
if(HuffNode[p].lchild==c)
cd.bit[cd.start]=0;/*左分支编码为0*/
else
cd.bit[cd.start]=1;
/*右分支编码为1*/
cd.start--;
c=p;
p=HuffNode[c].parent;
}
for(j=cd.start+1; j<n; j++) /*保存求出的每个叶结点的哈夫曼编码和编码的起始位*/
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
}
for (i=0; i<n; i++) /*输出每个叶子结点的哈夫曼编码*/
{
printf("%c: ",HuffNode[i].data);
for(j=HuffCode[i].start+1; j<n; j++)
printf("%d",HuffCode[i].bit[j]);
printf("\n");
}
}

int main()
{
HNodeType HuffNode[MAXNODE];
HCodeType HuffCode[MAXLEAF];
int n,i;
printf("create HuffmanTree:\n");
HuffmanTree(HuffNode,&n);
printf("\n");
fo