树的实验报告1Word文件下载.docx
《树的实验报告1Word文件下载.docx》由会员分享，可在线阅读，更多相关《树的实验报告1Word文件下载.docx（24页珍藏版）》请在冰点文库上搜索。
voidPreleaf（BTreeroot）;
先序求叶子节点个数
voidPrintfTree（BTreeroot,inth）;
打印二叉树
intPostHeight（BTreeroot））;
后序求树的深度
voidInitTree（BiTree*bt）;
初始化树
intInitStack（Stack*top）;
初始化栈
BiTnode*Create（）;
//扩展结点创建二叉树
intPush（Stack*top,BiTreep）;
入栈
intPop（Stack*top,BiTree*p）;
出栈
intGetTop（Stacktop,BiTreep）;
取栈顶元素
voidPreStack（BTreeroot）;
//非递归先序遍历
voidSelect（HTreeht,intpos/*寻找的范围*/,int*s1,int*s2）//查找最小的两个节点的下标
voidCreatHuffmanTree（HTreeht,intw[],intn）//创建哈夫曼树
voiOutput（HTreeht,intn）//输出哈夫曼树
voidCodeHuffmanTree（HTreeht,HCodehc,intn）//编码
voidOutputCode（HCodehc,intw[],intn）//输出编码
3、详细设计及运行结果
voidpreOrder（BiTreebt）//先序遍历。
{
if（bt!
=NULL）
{
printf（"
%c"
bt->
data）;
preOrder（bt->
LChild）;
RChild）;
}
}
voidInOrder（BiTreebt）//中序遍历。
InOrder（bt->
voidPostOrder（BiTreebt）//后序遍历。
PostOrder（bt->
voidTraver（BiTreebt）
intPostTreeDepth（BiTreebt）
inthl,hr,max;
hl=PostTreeDepth（bt->
hr=PostTreeDepth（bt->
max=hl>
hr?
hl:
hr;
return（max+1）;
else
return0;
voidPreStack（BiTreebt）//非递归遍历
BiTreep;
LinkStacks;
InitStack（&
s）;
//p=bt;
PushStack（s,bt）;
while（!
Isempty（s））
PopStack（s,&
p）;
printf（"
p->
if（p->
RChild!
=NULL）
PushStack（s,p->
LChild!
PushStack（s,p->
}
/*
voidPreStack（BiTreebt）//非递归先序遍历
p=bt;
while（p||!
if（p）
{
PushStack（s,p）;
p=p->
LChild;
else
PopStack（s,&
RChild;
}*/
voidPrintTree（BiTreebt,intnLayer）
inti;
if（bt==NULL）
return;
PrintTree（bt->
RChild,nLayer+1）;
for（i=0;
i<
nLayer;
i++）
"
）;
printf（"
%c\n"
LChild,nLayer+1）;
voidLeafTree（BiTreebt）//树的叶子结点遍历
if（bt->
LChild==NULL&
&
bt->
RChild==NULL）
LeafTree（bt->
voidTravel（BiTreebt）//树的按层遍历
LinkQueueQ;
InitQueue（&
Q）;
EnterQueue（&
Q,p）;
while（Q.front!
=Q.rear）
DeleteQueue（&
Q,&
if（p->
LChild）
EnterQueue（&
Q,p->
RChild）
2：
哈弗曼
voidCreat（HuffmanTreeht,intw[],charp[],intn）//构造哈弗曼树。
ints1,s2,i;
for（i=1;
=n;
i++）//前n个叶子结点的初始化
ht[i].weight=w[i];
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
for（i=n+1;
=2*n-1;
i++）//权值的初始化。
select（ht,i-1,&
s1,&
s2）;
ht[i].weight=ht[s1].weight+ht[s2].weight;
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].LChild=s1;
ht[i].RChild=s2;
//生成哈弗曼树的函数编码。
voidOrderHuffman（HuffmanTreeht,Huffmancodehc,charstr[],intm）//根据哈弗曼树构成哈弗曼编码表hc。
intq[N];
char*cd;
//临时存放编码串。
intc,p,i;
//c,p分别为孩子和双亲。
intstart;
//制定编码cd的起始位置。
cd=（char*）malloc（m*sizeof（char））;
cd[m-1]='
\0'
;
//最后一位置放上字符串的结束标志。
i=0;
while（i<
m）
switch（str[i]）
case'
s'
:
q[i]=3;
break;
t'
q[i]=4;
a'
q[i]=2;
e'
q[i]=6;
default:
break;
start=m-1;
c=q[i];
p=ht[q[i]].parent;
while（p!
=0）
--start;
if（ht[p].LChild==c）
cd[start]='
0'
//左孩子生成0
else//右孩子生成1
1'
c=p;
p=ht[p].parent;
hc[i]=（char*）malloc（（m-start）*sizeof（char））;
strcpy（hc[i],&
cd[start]）;
%s"
hc[i]）;
i++;
free（cd）;
voidprint（HuffmanTreeht,intn）
%4d%4d%4d\n"
ht[i].weight,ht[i].LChild,ht[i].RChild）;
4、调试情况，设计技巧及体会
1．对自己的设计进行评价，指出合理和不足之处，提出改进方案；
打印树状二叉树的模块没有能按照自然数的形式打印，有待改进。
2．对设计及调试过程的心得体会。
5、源程序清单（电子版）
建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。
1:
从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立），
2:
将此二叉树按照“树状形式”打印输出，
3:
对其进行遍历（先序、中序和后序），
4:
最后将遍历结果打印输出在遍历算法中
5:
要求至少有一种遍历采用非递归方法。
*/
#include<
stdio.h>
string.h>
stdlib.h>
#defineFALSE0
#defineTRUE1
typedefstructNode
chardata;
structNode*LChild;
structNode*RChild;
}BitNode,*BiTree;
typedefstructnod
BiTreeelem;
structnod*next;
}SeqStack,*LinkStack;
voidInitStack（LinkStack*top）
（*top）=（LinkStack）malloc（sizeof（SeqStack））;
（*top）->
next=NULL;
intIsempty（LinkStacktop）
if（top->
next==NULL）
returnTRUE;
returnFALSE;
intPushStack（LinkStacktop,BiTreex）
LinkStacktemp;
temp=（SeqStack*）malloc（sizeof（SeqStack））;
if（temp==NULL）
returnFALSE;
temp->
elem=x;
next=top->
next;
top->
next=temp;
returnTRUE;
intPopStack（LinkStacktop,BiTree*x）
temp=top->
*x=temp->
elem;
next=temp->
free（temp）;
intCreatBiTree（BiTree*bt）//树的先序建立
charch;
ch=getchar（）;
if（ch=='
#'
）
*bt=NULL;
*bt=（BitNode*）malloc（sizeof（BitNode））;
if（*bt==NULL）
return0;
（*bt）->
data=ch;
CreatBiTree（&
（（*bt）->
LChild））;
RChild））;
return1;
typedefstructnode
BiTreew;
structnode*next;
}LinkNode;
typedefstruct
LinkNode*front;
LinkNode*rear;
}LinkQueue;
intInitQueue（LinkQueue*Q）
Q->
front=（LinkNode*）malloc（sizeof（LinkNode））;
if（Q->
front!
Q->
rear=Q->
front;
front->
intEnterQueue（LinkQueue*Q,BiTreex）
LinkNode*NewNode;
NewNode=（LinkNode*）malloc（sizeof（LinkQueue））;
if（NewNode!
NewNode->
w=x;
rear->
next=NewNode;
rear=NewNode;
intDeleteQueue（LinkQueue*Q,BiTree*x）
LinkNode*p;
front==Q->
rear）
p=Q->
next=p->
rear==p）
*x=p->
w;
free（p）;
voidmain（）
BiTreebt;
intnLayer;
CreatBiTree（&
bt）;
nLayer=PostTreeDepth（bt）;
树的深度：
%d\n"
nLayer）;
树的树状打印：
\n"
PrintTree（bt,nLayer）;
前序访问：
preOrder（bt）;
中序访问：
InOrder（bt）;
后序访问：
PostOrder（bt）;
非递归访问：
PreStack（bt）;
树的叶子结点有:
LeafTree（bt）;
树的按层遍历：
Travel（bt）;
//huffman
#defineN20
#defineM2*N-1
typedefchar*Huffmancode[N+1];
intweight;
intparent;
intLChild;
intRChild;
}HTNode,HuffmanTree[M+1];
//建立哈弗曼树的几个函数。
voidselect（HuffmanTreeht,intpos,int*s1,int*s2）//寻找最小孩子形成最优二叉树。
intm1,m2;
m1=m2=32767;
=pos;
if（ht[i].parent==0&
ht[i].weight<
m1）
m2=m1;
m1=ht[i].weight;
*s2=*s1;
*s1=i;
elseif（ht[i].parent==0&
m2）
m2=ht[i].weight;
*s2=i;
if（*s1>
*s2）
i=*s1;
*s1=*s2;
*s2=i;
升级会员 