二叉树实验报告Word格式.docx
《二叉树实验报告Word格式.docx》由会员分享，可在线阅读，更多相关《二叉树实验报告Word格式.docx（15页珍藏版）》请在冰点文库上搜索。
（1）建立头文件InThread.h如下：
typedefstructNode
{
DataTypedata;
/*数据元素*/
intleftThread;
/*左线索*/
structNode*leftChild;
/*左指针*/
structNode*rightChild;
/*右指针*/
intrightThread;
/*右线索*/
}ThreadBiNode;
/*===================================*/
/*把一颗二叉树进行中序线索化的函数为CreatInThread（），*/
/*该函数把头结点进行了中序线索化，其余部分的中序线索化*/
/*是通过调用InThread（）函数实现的。
InThread（）是一个递归*/
/*函数。
*/
voidInThread（ThreadBiNode*current,ThreadBiNode**pre）
/*中序线索化二叉树*/
/*current为当前结点的指针，pre为当前结点的中序前驱结点指针*/
if（current!
=NULL）
{
InThread（current->
leftChild,pre）;
/*中序线索化左子树*/
if（current->
leftChild==NULL）
current->
leftThread=1;
/*建立左线索标记*/
leftChild=*pre;
/*建立左线索指针*/
}
elsecurrent->
leftThread=0;
rightChild!
rightThread=0;
rightThread=1;
if（（*pre）->
rightChild==NULL）
（*pre）->
/*建立右线索标记*/
rightChild=current;
/*建立右线索指针*/
*pre=current;
/*前序结点指针等于当前结点指针*/
rightChild,pre）;
/*中序线索化右子树*/
}
/*============================*/
/*创建中序线索化二叉树*/
voidCreatInThread（ThreadBiNode**root）
/*创建中序线索化二叉树tree*/
ThreadBiNode*t=*root;
/*保存原二叉树根结点指针*/
ThreadBiNode*current,*pre=*root;
/*建立头结点*/
*root=（ThreadBiNode*）malloc（sizeof（ThreadBiNode））;
if（t==NULL）/*当二叉树为空时*/
（*root）->
leftChild=*root;
rightChild=*root;
else/*当二叉树为非空时*/
current=t;
leftChild=t;
/*置头结点左指针*/
/*置头结点的左线索*/
InThread（current,&
pre）;
/*线索化二叉树*/
pre->
/*置最后一个结点的右指针*/
/*置最后一个结点的右线索*/
rightChild=pre;
/*置头结点的右指针*/
/*置头结点的右线索*/
typedefstruct
ThreadBiNode*root;
/*头指针*/
ThreadBiNode*current;
/*当前结点指针*/
intnextComplete;
/*遍历结束标记*/
}ThreadBiTree;
/*初始化中序线索二叉树*/
voidThreadInitiate（ThreadBiTree*tree,ThreadBiNode*root）
/*初始化中序线索二叉树*/
tree->
root=root;
current=root;
if（root==NULL）
nextComplete=1;
else
nextComplete=0;
/*使中序线索二叉树tree的当前结点指针指向中序遍历的第一个结点*/
voidFirst（ThreadBiTree*tree）
/*使中序线索二叉树tree的当前结点指针指向中序遍历的第一个结点*/
current=tree->
root;
while（tree->
current->
leftThread==0）
leftChild;
if（tree->
current==tree->
root）tree->
elsetree->
/*使中序线索二叉树tree的当前结点指针指向中序遍历的下一个结点*/
voidNext（ThreadBiTree*tree）
/*使中序线索二叉树tree的当前结点指针指向中序遍历的下一个结点*/
ThreadBiNode*p=tree->
rightChild;
nextComplete==1）return;
rightThread==0）
while（p->
leftThread==0）p=p->
current=p;
/*判断是否已到中序线索二叉树尾部函数*/
intEndOfNext（ThreadBiTree*tree）
/*如中序线索二叉树tree的nextComplete域值等于1，则表示已到尾部*/
returntree->
nextComplete;
（2）建立主函数程序为：
#include<
stdio.h>
stdlib.h>
malloc.h>
typedefcharDataType;
#include"
InThread.h"
ThreadBiNode*GetTreeNode（DataTypeitem,ThreadBiNode*left,ThreadBiNode*right）
ThreadBiNode*p;
p=（ThreadBiNode*）malloc（sizeof（ThreadBiNode））;
p->
data=item;
leftChild=left;
rightChild=right;
returnp;
voidMakeCharTree（ThreadBiNode**root）
ThreadBiNode*b,*c,*d,*e,*f,*g,*h;
g=GetTreeNode（'
G'
NULL,NULL）;
d=GetTreeNode（'
D'
e=GetTreeNode（'
E'
g,NULL）;
b=GetTreeNode（'
B'
d,e）;
h=GetTreeNode（'
H'
f=GetTreeNode（'
F'
NULL,h）;
c=GetTreeNode（'
C'
f,NULL）;
*root=GetTreeNode（'
A'
b,c）;
voidmain（void）
ThreadBiTreetree;
MakeCharTree（&
root）;
CreatInThread（&
printf（"
Binarytreetraversesequenceinorderis:
"
）;
ThreadInitiate（&
tree,root）;
for（First（&
tree）;
!
EndOfNext（&
Next（&
tree））
%c"
tree.current->
data）;
\n"
Thisprogramismadeby10273206!
}
运行结果为：
7-24
（1）建立头文件Haffman.h如下：
哈夫曼树的构造：
intweight;
intflag;
intparent;
intleftChild;
intrightChild;
}HaffNode;
intbit[MaxN];
intstart;
}Code;
voidHaffman（intweight[],intn,HaffNodehaffTree[]）
inti,j,m1,m2,x1,x2;
for（i=0;
i<
2*n-1;
i++）
if（i<
n）haffTree[i].weight=weight[i];
elsehaffTree[i].weight=0;
haffTree[i].parent=-1;
haffTree[i].flag=0;
haffTree[i].leftChild=-1;
haffTree[i].rightChild=-1;
n-1;
m1=m2=MaxValue;
x1=x2=0;
for（j=0;
j<
n+i;
j++）
if（haffTree[j].weight<
m1&
&
haffTree[j].flag==0）
m2=m1;
x2=x1;
m1=haffTree[j].weight;
x1=j;
elseif（haffTree[j].weight<
m2&
m2=haffTree[j].weight;
x2=j;
haffTree[x1].parent=n+i;
haffTree[x2].parent=n+i;
haffTree[x1].flag=1;
haffTree[x2].flag=1;
haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
haffTree[n+i].leftChild=x1;
haffTree[n+i].rightChild=x2;
哈夫曼编码的函数：
voidHaffmanCode（HaffNodehaffTree[],intn,CodehaffCode[]）
{
Code*cd=（Code*）malloc（sizeof（Code））;
inti,j,child,parent;
n;
cd->
start=n-1;
weight=haffTree[i].weight;
child=i;
parent=haffTree[i].parent;
while（parent!
=-1）
if（haffTree[parent].leftChild==child）
bit[cd->
start]=0;
start]=1;
start--;
child=parent;
parent=haffTree[child].parent;
for（j=cd->
start+1;
haffCode[i].bit[j]=cd->
bit[j];
haffCode[i].start=cd->
haffCode[i].weight=cd->
weight;
（2）运行的程序：
#defineMaxValue10000
#defineMaxBit10
#defineMaxN100
Haffman.h"
inti,j,n=4;
intweight[]={1,3,5,7};
HaffNode*myHaffTree=（HaffNode*）malloc（sizeof（HaffNode）*（2*n+1））;
Code*myHaffCode=（Code*）malloc（sizeof（Code）*n）;
if（n>
MaxN）
Error!
exit（0）;
Haffman（weight,n,myHaffTree）;
HaffmanCode（myHaffTree,n,myHaffCode）;
Weight=%dCode="
myHaffCode[i].weight）;
for（j=myHaffCode[i].start;
%d"
myHaffCode[i].bit[j]）;
\n"
Thisprogramismadeby10273206\n"
（3）第一步：
第二步：
第三步：
第四步：
总结与思考：
明白了图文并茂的形象，二叉树让我更好地理解程序代码。
熟悉了二叉树结点的结构和对二树的基本操作，熟练的掌握二叉树的先序递归遍历、中序递归和非递归遍历、后序递归遍历常用遍历方法，掌握了哈夫曼树的构造方法及哈夫曼编码。
升级会员 