《LAB06 二叉树的操作及应用》由会员分享，可在线阅读，更多相关《LAB06 二叉树的操作及应用（20页珍藏版）》请在金锄头文库上搜索。
1、 算法与数据结构算法与数据结构实验报告实验报告- 1 -Lab06二叉树的操作及应用二叉树的操作及应用【实验目的和要求实验目的和要求】1掌握二叉树顺序存储表示的实现及其基本操作；2掌握线索二叉树类型的定义方法，会按对称序线索化二叉树和周游对称序线索二叉树；3掌握优先队列的实现及其基本操作；4掌握构造哈夫曼树的基本思想和哈夫曼树的数据结构设计，能编程实现哈夫曼树的构造；5掌握哈夫曼树的基本应用哈夫曼编码。【实验内容实验内容】1二叉树按顺序存储表示，编写一个 C 源程序，计算给定二叉树的叶结点数，并给出它的先根序列，或后根序列，或对称序列。2编写一个 C 源程序，对给定的二叉树，按对称序线索化该二
2、叉树，并按对称序周游该对称序线索二叉树。3. 编写一个 C 源程序，恰当定义优先队列，并对给定的优先队列，实现插入和删除最小结点的操作。4简述构造哈夫曼树的基本思想和哈夫曼树的数据结构设计，并编程实现哈夫曼树的构造。5简述哈夫曼编码的原理和方法，编程实现哈夫曼编码与解码。【实验仪器与软件实验仪器与软件】 1CPU 主频在 1GHz 以上，内存在 512Mb 以上的 PC；2VC6.0，Word 2003 及以上版本。实验讲评：实验讲评：实验成绩：实验成绩： 评阅教师：2012 年 月 日算法与数据结构算法与数据结构实验报告实验报告- 2 -Lab06二叉树的操作及应用二叉树的操作及应用一、顺序
3、存储表示二叉树及其基本运算其顺序表示为：首先要对它进行扩充，增加一些并不存在其顺序表示为：首先要对它进行扩充，增加一些并不存在其顺序表示为：首先要对它进行扩充，增加一些并不存在其顺序表示为：首先要对它进行扩充，增加一些并不存在的空结点，使之成为一棵完全二叉树，然后再用一维数组的空结点，使之成为一棵完全二叉树，然后再用一维数组的空结点，使之成为一棵完全二叉树，然后再用一维数组的空结点，使之成为一棵完全二叉树，然后再用一维数组顺序存储。顺序存储。顺序存储。顺序存储。其存储表示为：其存储表示为：其存储表示为：structstructstructstruct SeqBinTree/*SeqBinTre
4、e/*SeqBinTree/*SeqBinTree/* 顺序二叉树类型定义顺序二叉树类型定义顺序二叉树类型定义顺序二叉树类型定义*/*/*/*/intintintint MAXNUMMAXNUMMAXNUMMAXNUM /*/*/*/* 完全二叉树中允许结点的最大个数完全二叉树中允许结点的最大个数完全二叉树中允许结点的最大个数完全二叉树中允许结点的最大个数*/*/*/*/intintintint n;n;n;n; /*/*/*/* 改造成完全二叉树后，结点的实际个数改造成完全二叉树后，结点的实际个数改造成完全二叉树后，结点的实际个数改造成完全二叉树后，结点的实际个数*/*/*/*/DataTy
5、peDataTypeDataTypeDataType *nodelist;*nodelist;*nodelist;*nodelist; /*/*/*/* 存放结点的数组存放结点的数组存放结点的数组存放结点的数组*/*/*/*/;typedeftypedeftypedeftypedef structstructstructstruct SeqBinTreeSeqBinTreeSeqBinTreeSeqBinTree *PSeqBinTree;*PSeqBinTree;*PSeqBinTree;*PSeqBinTree; 二、对称序线索化该二叉树及其周游的实现要按对称序周游对称序线索二叉树，首先找
6、到对称序列中的第要按对称序周游对称序线索二叉树，首先找到对称序列中的第要按对称序周游对称序线索二叉树，首先找到对称序列中的第要按对称序周游对称序线索二叉树，首先找到对称序列中的第一个结点，然后依次找到结点的后继结点，直至其后继结点为一个结点，然后依次找到结点的后继结点，直至其后继结点为一个结点，然后依次找到结点的后继结点，直至其后继结点为一个结点，然后依次找到结点的后继结点，直至其后继结点为空即可。空即可。空即可。空即可。第一个结点也很容易找，只要从根结点出发沿着左指针不第一个结点也很容易找，只要从根结点出发沿着左指针不第一个结点也很容易找，只要从根结点出发沿着左指针不第一个结点也很容易找，只
7、要从根结点出发沿着左指针不断往下走，直至左指针为空，到达断往下走，直至左指针为空，到达断往下走，直至左指针为空，到达断往下走，直至左指针为空，到达“最左下最左下最左下最左下”的结点，这就是的结点，这就是的结点，这就是的结点，这就是对称序第一个结点。对称序第一个结点。对称序第一个结点。对称序第一个结点。找任意结点的对称序后继时，也非常容易做：一个结点的找任意结点的对称序后继时，也非常容易做：一个结点的找任意结点的对称序后继时，也非常容易做：一个结点的找任意结点的对称序后继时，也非常容易做：一个结点的右指针字段如果是线索，则它就指向该结点在对称序下的后继；右指针字段如果是线索，则它就指向该结点在对
8、称序下的后继；右指针字段如果是线索，则它就指向该结点在对称序下的后继；右指针字段如果是线索，则它就指向该结点在对称序下的后继；算法与数据结构算法与数据结构实验报告实验报告- 3 -如果不是线索，则它指向该结点右子树的根，而该结点在对称如果不是线索，则它指向该结点右子树的根，而该结点在对称如果不是线索，则它指向该结点右子树的根，而该结点在对称如果不是线索，则它指向该结点右子树的根，而该结点在对称序下的后继应是此右子树的最左下结点。序下的后继应是此右子树的最左下结点。序下的后继应是此右子树的最左下结点。序下的后继应是此右子树的最左下结点。其编写程序如下：其编写程序如下：#include#inclu
9、de#include#include#define#define MAX_SIZEMAX_SIZE 100100#define#define LinkLink 0 0#define#define ThreadThread 1 1typedeftypedef structstruct BiThrTreeNodeBiThrTreeNode charchar info;info;structstruct BiThrTreeNodeBiThrTreeNode *l_link;*l_link;structstruct BiThrTreeNodeBiThrTreeNode *r_link;*r_link;
10、intint LTag,RTag;LTag,RTag;BiThrTreeNode,*BiThrTree;BiThrTreeNode,*BiThrTree;typedeftypedef structstruct SeqStackSeqStack BiThrTreeBiThrTree sMAX_SIZE;sMAX_SIZE;intint t;t;*PSeqStack;*PSeqStack;PSeqStackPSeqStack createEmptyStack_seq(void)createEmptyStack_seq(void) 算法与数据结构算法与数据结构实验报告实验报告- 4 -PSeqSta
11、ckPSeqStack p_stack;p_stack;p_stack=(PSeqStack)malloc(sizeof(structp_stack=(PSeqStack)malloc(sizeof(struct SeqStack);SeqStack);if(NULL=p_stack)if(NULL=p_stack) printf(“nprintf(“n outout ofof space!n“);space!n“);exit(-1);exit(-1); elseelse p_stack-t=-1;/p_stack-t=-1;/表示以满堆栈的方式存放数据表示以满堆栈的方式存放数据 return
12、return p_stack;p_stack; intint isEmptyStack_seq(PSeqStackisEmptyStack_seq(PSeqStack p_stack)p_stack) returnreturn p_stack-t=-1;p_stack-t=-1; voidvoid push_seq(PSeqStackpush_seq(PSeqStack p_stack,BiThrTreep_stack,BiThrTree bt)bt) if(p_stack-t=MAX_SIZE-1)if(p_stack-t=MAX_SIZE-1)算法与数据结构算法与数据结构实验报告实验报告-
13、 5 - printf(“tOverflow!n“);printf(“tOverflow!n“);exit(-1);exit(-1); +p_stack-t;+p_stack-t;p_stack-sp_stack-t=bt;p_stack-sp_stack-t=bt; voidvoid pop_seq(PSeqStackpop_seq(PSeqStack p_stack)p_stack) if(p_stack-t=-1)if(p_stack-t=-1) printf(“tUnderflow!n“);printf(“tUnderflow!n“);exit(-1);exit(-1); -p_sta
14、ck-t;-p_stack-t; BiThrTreeBiThrTree top_seq(PSeqStacktop_seq(PSeqStack p_stack)p_stack) if(isEmptyStack_seq(p_stack)if(isEmptyStack_seq(p_stack) printf(“tNoprintf(“tNo data!n“);data!n“); 算法与数据结构算法与数据结构实验报告实验报告- 6 -returnreturn p_stack-sp_stack-t;p_stack-sp_stack-t; BiThrTreeBiThrTree createBiThrTree
15、()createBiThrTree() /先序创建二叉树先序创建二叉树 charchar ch;ch;BiThrTreeBiThrTree T;T;scanf(“%c“,scanf(“%c“,getchar();getchar();if(ch=#)if(ch=#)T=NULL;T=NULL;elseelse T=(BiThrTree)malloc(sizeof(BiThrTreeNode);T=(BiThrTree)malloc(sizeof(BiThrTreeNode);if(!T)if(!T)exit(0);exit(0);T-info=ch;T-info=ch;T-LTag=Link;T-LTag=Link;T-RTag=Link;T-RTag=Link;T-l_link=createBiThrTree();T-l_link=createBiThrTree();T-r_link=createBiThrTree();T-r_link=createBiThrTree(); returnret
