二叉树系列算法及哈弗曼编、译码
实验报告
——二叉树系列算法及哈弗曼编、译码
一．需求分析
1，二叉树的系列算法：先序初始化二叉树，先序、中序、后续的递归算法遍历二叉树，中序非递归算法遍历二叉树，层次遍历二叉树（自创），求二叉树的深度（自创），返回或修改任意节点的值（自创），常规二叉树找某节点的双亲结点（中序），先序线索化二叉树等。
2，实现哈夫曼编码的生成算法，以及译码的解释算法。
3，本程序的实验目的是为了使学生熟练掌握二叉树的原理及各种算法，熟练掌握哈夫曼编、译码的方法。
测试数据：（附后）
二．概要设计：
1、抽象数据类型如下：
ADT Tree{
数据对象D：D是具有相同特性的数据元素集合。
数据关系R：若D为空集，则成为空树；
若D仅含有一个数据元素，则R为空集，否则R={H}，H是如下二元关系：（1）在D中存在唯一的称之为跟的元素ROOT，它在关系H下无前驱；
（2）若D-{ROOT}≠?，则存在D-{ROOT}的一个划分D1,D2,……Dm(m>0)，对任意的j≠k（1≤j,k≤m）有Dj∩Dk=?,且对任意的i（1≤i≤m），唯一存在数据Xi∈Di,有
（3）对应D-{ROOT}的划分，H-{
}
（4）存储结构如下：
//定义binarytree的存储结构
typedef struct BiTree
{
char data;
struct BiTree *lchild,*rchild;
}BiTree,*BiTree_Z;
//定义线索化二叉树的储存结构
typedef enum PointerTag{Link,Thread}; //Link==0表示指针，Thread==1表示线索
typedef struct BiThrNode
{
char data;
struct BiThrNode *lchild,*rchild;
PointerTag LTag,RTag;
}BiThrNode,*BiThrTree;
//定义哈弗曼编码的存储结构
typedef struct
{
int weight; //权值
int lchild,rchild,parent; //双亲，左右孩子在数组中的位置
}HuffNode,*HuffmanTree; //使用动态分配数组来存储哈弗曼树
typedef char * *HuffmanCode; //使用动态分配数组来存储哈弗曼编码2、基本操作：
BiTree * InitBiTree();
int PreOrderTraverse(BiTree *T,int (*Visit)(char e));
int Visit(char e);
int InOrderTraverse(BiTree *T,int (* Visit)(char e));
int PostOrderTraverse(BiTree *T,int (* Visit)(char e));
int InOrderTraverse_2(BiTree *T,int (* Visit)(char e));
int CreateStack(Stack &S);
void push(Stack &S,BiTree_Z T);
int Pop(Stack &S,BiTree_Z &T);
int GetTop(Stack &S,BiTree_Z &T);
int LevelOrderTraverse(BiTree *T,int (* Visit)(char(e)));
int BiTreeDepth(BiTree *T);
void Root(BiTree *T);
void Value(BiTree *T);
void Assign(BiTree *T);
int Parients(BiTree *T,int (* Visit)(char e));
//线索化二叉树
BiThrTree InitBiThrTree();
int InOrderThreading(BiThrTree &Thrt,BiThrTree T);
int InOrderTraverse_Thr(BiThrTree T,int (* Visit)(char e));
//哈弗曼编、译码操作
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n); void HuffmanDecoding(HuffmanTree &HT,int n,char *chars,int (* Visit)(int w));
int Visit(int w);
3，主程序
Void main()
{
初始化；
do{
接受命令；处理命令
}
}while(‘命令’=‘退出’)；
4,本程序有三个模块，调用关系为：
主程序模块
头文件模块
三、详细设计
详细的代码在打包文件，这里只提及自己编写的一些代码：
1、层次遍历：
int LevelOrderTraverse(BiTree *T,int (* Visit)(char(e))) {
if(!T) return ERRO;
Stack S,D;//S为栈，D为队列
BiTree_Z *pre,p;
int i;
i=CreateStack(S);
i=CreateStack(D);
//先把T入栈和队列
push(S,T);
push(D,T);
while(S.base!=S.top)
{
int j=0;
while(S.base!=S.top)//S中所有元素出栈
{
i=Pop(S,p);
if(p->lchild)
{
push(D,p->lchild);
j++;
}
if(p->rchild)
{
push(D,p->rchild);
j++;
} //如果p有左右子树，那就入队列先左后右}
pre=D.top;
//再把D中刚才加入的j个元素由顶到底入栈S
for(i=1;i<=j;i++)
{
push(S,*(pre-i));
}
}
//对D进行先入先出的原则出栈
while(D.base { i=Visit((*D.base)->data); D.base+=1; } } 2、常规二叉树找某节点的双亲结点（中序）： //找出某一个结点的双亲结点(中序) int Parients(BiTree *T,int (* Visit)(char e)) { printf("请输入结点值：\n"); getchar(); char c; scanf("%c",&c); Stack S; BiTree_Z p; int i; i=CreateStack(S); push(S,T); if(c==T->data) { printf("此为根结点，无双亲结点\n"); return ERRO; } while(!(S.top==S.base)) { //走到最左端 while(GetTop(S,p)&&p) { if(p->lchild) { if(p->lchild->data==c) { printf("该节点的双亲结点为：\n"); Visit(p->data); return OK; } } if(p->rchild) { if(p->rchild->data==c) { printf("该节点的双亲结点为：\n"); Visit(p->data); return OK; } } p=p->lchild; push(S,p); } //这必须有一个空指针退栈 i=Pop(S,p); if(!(S.base==S.top)) //右子树是一步一步访问的所以用if { //先出栈 Pop(S,p); //访问节点并看节点data值是否问空 if(p->lchild) { if(p->lchild->data==c) { printf("该节点的双亲结点为：\n"); Visit(p->data); return OK; } } if(p->rchild) { if(p->rchild->data==c) { printf("该节点的双亲结点为：\n"); Visit(p->data); return OK; } } //右子树入栈 push(S,p->rchild); } } } 3、哈弗曼编码中的Select函数： void Select(HuffmanTree &HT,int i,int *s1,int *s2) { HT[(*s1)].weight=1000; HT[(*s1)].weight=1000; int j; for(j=1;j { if(HT[j].parent==0&&HT[(*s1)].weight>HT[j].weight) //判断是否是未被编码的结点 { *s1=j; } } for(j=1;j { if(HT[j].parent==0&&HT[(*s2)].weight>HT[j].weight&&j!=(*s1)) { *s2=j; } } } 4，哈弗曼译码： void HuffmanDecoding(HuffmanTree &HT,int n,char *chars,int (* Visit)(int w)) { int len=strlen(chars); int i,m=2*n-1; int c=m; for(i=0;i<=len;i++) { if(!HT[c].lchild) { Visit(HT[c].weight); c=m; i--;//注意这儿一定得给i减，因为到达叶子结点后，不需要读编码，但此时i已经加了。。。 } else { if(chars[i]=='0') c=HT[c].lchild; if(chars[i]=='1') c=HT[c].rchild; } } printf("\n"); } 四、设计和调试 1，通过这次大量的编译二叉树相关代码，充分认识了一些递归的思想，以及，递归与非递归算法的相互转换，受益匪浅。 2，在编译哈弗曼编、译码的过程中，发现自己的指针方面的知识有所欠缺，又回头学习了指针的相关知识，了解到右左法则等技巧。 五、用户手册 1. 本程序的运行环境为Windows 的C++6.0 2. 两个程序的主函数采用了While循环，除非输入0，否则不会退出程序。 3. 在二叉树程序中，先序初始化完二叉树后，可以一次性输出先序、中序、后续、层序二叉树结点序列。 4. 在哈弗曼编、译码程序中，已经给定了各个字母的权值，以及一串哈弗曼编码。必须先进行编码，才能进行译码。 六、测试结果： 1.、二叉树的测试结果： 2、哈弗曼编、译码测试结果： 实验报告 课程名称数据结构 实验项目实验三--创建一个二叉树并输出三种遍历结果 系别■计算机学院 _________________ 专业_______________ 班级/学号_____________ 学生姓名___________ 实验日期— 成绩______________________________ 指导 教师 实验题目：实验三创建一个二叉树并输出三种遍历结果 实验目的 1）掌握二叉树存储结构； 2）掌握并实现二叉树遍历的递归算法和非递归算法; 3）理解树及森林对二叉树的转换; 4）理解二叉树的应用一哈夫曼编码及WPL计算。 实验内容 1）以广义表或遍历序列形式创建一个二叉树，存储结构自选； 2）输出先序、中序、后序遍历序列； 3）二选一应用题：1）树和森林向二叉树转换；2）哈夫曼编码的应用问题。 题目可替换上述前两项实验内容） 设计与编码 1）程序结构基本设计框架 （提示：请根据所选定题目，描述程序的基本框架，可以用流程图、界面描述图、 框图等来表示） 2）本实验用到的理论知识遍历二叉树，递归和非递归的方法 （应用型 (提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法) 3) 具体算法设计 1) 首先，定义二叉树的存储结构为二叉链表存储，每个元素的数 据类型Elemtype,定义一棵二叉树，只需定义其根指针。 2) 然后以递归的先序遍历方法创建二叉树，函数为CreateTree()，在输 入字符时要注意,当节点的左孩子或者右孩子为空的时候,应当输入一 个特殊的字符(本算法为“ #”),表示左孩子或者右孩子为空。 3) 下一步,创建利用递归方法先序遍历二叉树的函数,函数为 PreOrderTreeQ,创建非递归方法中序遍历二叉树的函数，函数为 InOrderTree()，中序遍历过程是：从二叉树的根节点开始，沿左子树 向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后，从 栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依次类 推，指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的 函数，函数为LaOrderTree()。 (提示：该部分主要是利用C、C++ 等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述) 4) 编码 #include 昆明理工大学信息工程与自动化学院学生实验报告 （201 —201 学年第一学期） 课程名称：算法设计与分析开课实验室：年月日 一、上机目的及内容 1.上机内容 设需要编码的字符集为{d1, d2, …, dn}，它们出现的频率为{w1, w2, …, wn}，应用哈夫曼树构造最短的不等长编码方案。 2.上机目的 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）证明哈夫曼树满足最优子结构性质； （2）设计贪心算法求解哈夫曼编码方案； （3）设计测试数据，写出程序文档。 数据结构与算法: typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码 typedef struct { unsigned int weight; //用来存放各个结点的权值 unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针 } HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树 程序流程图： 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 程序代码： #include 二叉树的各种算法.txt男人的承诺就像80岁老太太的牙齿，很少有真的。你嗜烟成性的时候，只有三种人会高兴，医生你的仇人和卖香烟的。 /*用函数实现如下二叉排序树算法： （1）插入新结点 （2）前序、中序、后序遍历二叉树 （3）中序遍历的非递归算法 （4）层次遍历二叉树 （5）在二叉树中查找给定关键字(函数返回值为成功1,失败0) （6）交换各结点的左右子树 （7）求二叉树的深度 （8）叶子结点数 Input 第一行：准备建树的结点个数n 第二行：输入n个整数，用空格分隔 第三行：输入待查找的关键字 第四行：输入待查找的关键字 第五行：输入待插入的关键字 Output 第一行：二叉树的先序遍历序列 第二行：二叉树的中序遍历序列 第三行：二叉树的后序遍历序列 第四行：查找结果 第五行：查找结果 第六行~第八行：插入新结点后的二叉树的先、中、序遍历序列 第九行：插入新结点后的二叉树的中序遍历序列(非递归算法) 第十行：插入新结点后的二叉树的层次遍历序列 第十一行~第十三行：第一次交换各结点的左右子树后的先、中、后序遍历序列 第十四行~第十六行：第二次交换各结点的左右子树后的先、中、后序遍历序列 第十七行：二叉树的深度 第十八行：叶子结点数 */ #include "stdio.h" #include "malloc.h" #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int KeyType; #define STACK_INIT_SIZE 100 // 存储空间初始分配量 #define STACKINCREMENT 10 // 存储空间分配增量 #define MAXQSIZE 100 typedef int ElemType; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild;//左右孩子指针 } BiTNode,*BiTree; Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p) { if(!T){p=f;return FALSE;} else if(key==T->data){p=T;return TRUE;} else if(key 实验四 哈夫曼编码的贪心算法设计（4学时） [实验目的] １. 根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法; ２. 编程实现哈夫曼编译码器; ３. 掌握贪心算法的一般设计方法。 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。 核心源代码 #include //选择两个parent为0，且weight最小的结点s1和s2 void Select(HuffmanTree *ht,int n,int *s1,int *s2) { int i,min; for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { min=i; break; } } for(i=1; i<=n; i++) { if((*ht)[i].parent==0) { if((*ht)[i].weight<(*ht)[min].weight) min=i; } } *s1=min; for(i=1; i<=n; i++) 实验课题一：将下图中得二叉树用二叉链表表示： 1用三种遍历算法遍历该二叉树，给出对应得输出结果; 2写一个函数对二叉树搜索,若给出一个结点，根据其就是否属于该树，输出tｒｕe或者f ａｌse。 3写函数完成习题4、31(Ｃ＋+版)或4、2８（C版教科书）。 #iｎclｕde "stdio、h＂ ＃incluｄe”mallｏc、h" typedｅfｓtruct BｉTＮode ｛ cｈar data; sｔrucｔBiTＮode *lｃｈild,*rｃhiｌd; }ＢiTＮodｅ，*BiTrｅe； BｉＴree Creaｔe（BｉTｒeｅT) ｛ char ch； ch=getchａｒ(）; ｉｆ(ch=='#’） T=NULL; elｓe { T=(BiＴNode *）maｌloc(sｉｚｅｏf（ＢiTNｏｄe)）; Ｔ-〉data=ｃh； Ｔ-＞lｃｈiｌd=Creaｔe(T—〉lchilｄ); T—〉rchild=Creａte(Ｔ－〉rchｉld）； ｝ retuｒn Ｔ； } ｉnt node(BiＴrｅe Ｔ) { int sum1=0，a,b; ?iｆ（T) ｛ if（Ｔ！=ＮUＬL） ??sｕm1++; ?ａ=ｎode（Ｔ->lchiｌd); sｕm1＋=ａ； b=node(T—>rchｉld)； sum1+=b; ?} ｒetｕrn sum1； } int mｎode（BiTree T） { ?int sum２=0,ｅ，ｆ； if（T) { ?ｉf（（T->lcｈiｌd!=NULL）&＆(T－〉rchild!=NULL）)?sum2++； ?e=ｍnoｄｅ（Ｔ－〉lchild); suｍ2＋=e; f＝mnoｄｅ（T－〉rchｉｌd)； sum２+=f； ?｝ retｕrn sum2; ｝ void Preorｄer（BiTree T) { ｉf(Ｔ） { pｒintf（＂%c”，T－>daｔa)； Ｐreoｒder(Ｔ—>lchiｌｄ）； Ｐreorder（T－〉rchｉld）； ｝ } iｎt Sumｌeaｆ（BiTｒｅe T) { int suｍ=0,m，n; if（T） { if((！T-〉lchild）&&（!T-〉rｃhiｌd)) sum++； m=Ｓuｍleaf（T－>lchｉld)； suｍ+=m； n=Sumleaf(T—＞rｃhｉｌd); suｍ+＝ｎ； ｝ retuｒn ｓum； } 实验三树的应用 一.实验题目： 树的应用——哈夫曼编码 二.实验内容： 利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。 三、程序源代码: #include 二叉树遍历算法的实现 题目：编制二叉树遍历算法的实现的程序 一．需求分析 1.本演示程序中，二叉树的数据元素定义为非负的整型（unsigned int）数据，输 入-1表示该处没有节点 2.本演示程序输入二叉树数据均是按先序顺序依次输入 3.演示程序以用户和计算机对话方式执行，即在计算机终端上显示“提示信息” 之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运 算结果显示在其后 4.本实验一共包括三个主要程序，分别是：1）二叉树前序，中序，后序遍历递归 算法实现2）二叉树前序中序遍历非递归算法实现3)二叉树层次遍历算法实现 5.本程序执行命令包括：1）构建二叉树2）二叉树前序递归遍历3）二叉树中序 递归遍历4）二叉树后序递归遍历5）二叉树前序非递归遍历6）二叉树中序非 递归遍历7）二叉树层次遍历 6.测试数据 （1）7 8 -1 9 10 -1 -1 -1 6 11 -1 -1 12 13 -1 -1 14 -1 -1 （2）1 -1 -1 （3）7 8 -1 -1 9 -1 -1 二．概要设计 1.为实现二叉树的遍历算法，我们首先给出如下抽象数据类型 1）二叉树的抽象数据类型 ADT BiTree{ 数据对象D:D是具有相同特性的数据元素的集合 数据关系R： 若D=Φ，则R=Φ，称BiTree是空二叉树； 若D≠Φ，则R={H}，H是如下二元关系： (1)在D中存在唯一的成为根的数据元素root，它在关系H下无前驱； (2)若D-{H}≠Φ，则存在D-{root}={D1,D r}，且D1∩D r=Φ (3)若D1≠Φ，则D1中存在唯一的元素x1， #include if((*ht)[i].weight < (*ht)[min].weight) min = i; } } *s2 = min; } void CrtHuffmanTree(HuffmanTree *ht , int *w, int n) { /* w存放已知的n个权值，构造哈夫曼树ht */ int m,i; int s1,s2; m=2*n-1; *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ for(i=1;i<=n;i++) {/*1-n号放叶子结点，初始化*/ (*ht)[i].weight = w[i]; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } for(i=n+1;i<=m;i++) { (*ht)[i].weight = 0; (*ht)[i].LChild = 0; (*ht)[i].parent = 0; (*ht)[i].RChild = 0; } /*非叶子结点初始化*/ /* ------------初始化完毕！对应算法步骤1---------*/ for(i=n+1;i<=m;i++) /*创建非叶子结点,建哈夫曼树*/ { /*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/ select(ht,i-1,&s1,&s2); (*ht)[s1].parent=i; (*ht)[s2].parent=i; (*ht)[i].LChild=s1; (*ht)[i].RChild=s2; (*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight; } }/*哈夫曼树建立完毕*/ void outputHuffman(HuffmanTree HT, int m) { if(m!=0) { 二叉树实验报告 09信管石旭琳 20091004418 一、实验目的： 1、理解二叉树的遍历算法及应用 2、理解哈夫曼树及其应用。 3、掌握哈夫曼编码思想。 二、实验内容： 1、建立二叉树二叉链表 2、实现二叉树递归遍历算法（中序、前序、后序） 3、求二叉树高度 4、求二叉树结点个数 5、求二叉树叶子个数 6、将序号为偶数的值赋给左子树 三、主要程序： #include 数据结构（双语） ——项目文档报告用两种方式实现表达式自动计算 专业： 班级： 指导教师： 姓名： 学号： 目录 一、设计思想 (01) 二、算法流程图 (02) 三、源代码 (04) 四、运行结果 (11) 五、遇到的问题及解决 (11) 六、心得体会 (12) 一、设计思想 二叉树的遍历分为三种方式，分别是先序遍历，中序遍历和后序遍历。先序遍历实现的顺序是：根左右，中序遍历实现的是：左根右，后续遍历实现的是：左右根。根据不同的算法分，又分为递归遍历和非递归遍历。 递归算法： 1．先序遍历：先序遍历就是首先判断根结点是否为空，为空则停止遍历，不为空则将左子作为新的根结点重新进行上述判断，左子遍历结束后，再将右子作为根结点判断，直至结束。到达每一个结点时，打印该结点数据，即得先序遍历结果。 2.中序遍历：中序遍历是首先判断该结点是否为空，为空则结束，不为空则将左子作为根结点再进行判断，打印左子，然后打印二叉树的根结点，最后再将右子作为参数进行判断，打印右子，直至结束。 3.后续遍历：指针到达一个结点时，判断该结点是否为空，为空则停止遍历，不为空则将左子作为新的结点参数进行判断，打印左子。左子判断完成后，将右子作为结点参数传入判断，打印右子。左右子判断完成后打印根结点。 非递归算法： 1.先序遍历：首先建立一个栈，当指针到达根结点时，打印根结点，判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈，将左子作为新的根结点进行判断，方法同上。若当前结点没有左子，则直接将右子打印，同时将右子作为新的根结点判断。若当前结点没有右子，则打印左子，同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子，则当前结点为叶子结点，此时将从栈中出栈一个元素，作为当前的根结点，打印结点元素，同时将当前结点同样按上述方法判断，依次进行。直至当前结点的左右子都为空，且栈为空时，遍历结束。 2.中序遍历：首先建立一个栈，定义一个常量flag（flag为0或者1），用flag记录结点的左子是否去过，没有去过为0，去过为1，默认为0.首先将指针指向根结点，将根结点入栈，然后将指针指向左子，左子作为新的结点，将新结点入栈，然后再将指针指向当前结点的左子，直至左子为空，则指针返回，flag置1，出栈一个元素，作为当前结点，打印该结点，然后判断flag，flag为1则将指针指向当前结点右子，将右子作为新的结点，结点入栈，再次进行上面的判断，直至当前结点右子也为空，则再出栈一个元素作为当前结点，一直到结束，使得当前结点右子为空，且栈空，遍历结束。 3.后续遍历：首先建立两个栈，然后定义两个常量。第一个为status，取值为0，1，2.0代表左右子都没有去过，1代表去过左子，2，代表左右子都去过，默认为0。第二个常量为flag，取值为0或者1，0代表进左栈，1代表进右栈。初始时指针指向根结点，判断根结点是否有左子，有左子则，将根结点入左栈，status置0，flag置0，若没有左子则判断结点有没有右子，有右子就把结点入右栈，status置0，flag置1，若左右子都没有，则打印该结点，并将指针指向空，此时判断flag，若flag为0，则从左栈出栈一个元素作为当前结点，重新判断；若flag为1则从右栈出栈一个元素作为当前结点，重新判断左右子是否去过，若status 为1，则判断该结点有没有右子，若有右子，则将该结点入右栈，status置1，flag置1，若没有右子，则打印当前结点，并将指针置空，然后再次判断flag。若当前结点status为2，且栈为空，则遍历结束。若指针指向了左子，则将左子作为当前结点，判断其左右子情况，按上述方法处理，直至遍历结束。 #include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 100 //栈存储空间初始分配量 #define STACKINCREMENT 10 //存储空间分配增量 //------二叉树的存储结构表示------// typedef struct BiTNode{ int data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //-----顺序栈的存储结构表示------// typedef struct{ BiTree *top; BiTree *base; int stacksize; }SqStack; //*************************************************** //构造一个空栈s SqStack *InitStack(); //创建一颗二叉树 BiTree CreatBiTree(); //判断栈空 int StackEmpty(SqStack *S); //插入元素e为新的栈顶元素 void Push(SqStack *S,BiTree p); //若栈不为空，则删除s栈顶的元素e，将e插入到链表L中void Pop(SqStack *S,BiTree *q); //非递归先序遍历二叉树 void PreOrderTraverse(BiTree L); //非递归中序遍历二叉树 void InOrderTraverse(BiTree L); //非递归后序遍历二叉树 void PostOrderTraverse(BiTree L); //递归后序遍历二叉树 void PostOrder(BiTree bt); //递归中序遍历二叉树 void InOrder(BiTree bt); //递归先序遍历二叉树 void PreOrder(BiTree bt); //*************************************************** 0023算法笔记——【贪心算法】哈夫曼编码问题 1、问题描述 哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。一个包含100,000个字符的文件，各字符出现频率不同，如下表所示。 有多种方式表示文件中的信息，若用0,1码表示字符的方法，即每个字符用唯一的一个0,1串表示。若采用定长编码表示，则需要3位表示一个字符，整个文件编码需要300,000位；若采用变长编码表示，给频率高的字符较短的编码；频率低的字符较长的编码，达到整体编码减少的目的，则整个文件编码需要（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000位，由此可见，变长码比定长码方案好，总码长减小约25%。 前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。这种编码称为前缀码。编码的前缀性质可以使译码方法非常简单；例如001011101可以唯一的分解为0,0,101,1101，因而其译码为aabe。 译码过程需要方便的取出编码的前缀，因此需要表示前缀码的合适的数据结构。为此，可以用二叉树作为前缀码的数据结构：树叶表示给定字符；从树根到树叶的路径当作该字符的前缀码；代码中每一位的0或1分别作为指示某节点到左儿子或右儿子的“路标”。 从上图可以看出，表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子。图a表示定长编码方案不是最优的，其编码的二叉树不是一棵完全二叉树。在一般情况下，若C是编码字符集，表示其最优前缀码的二叉树中恰有|C|个叶子。每个叶子对应于字符集中的一个字符，该二叉树有|C|-1个内部节点。 给定编码字符集C及频率分布f,即C中任一字符c以频率f(c)在数据文件中出现。C的一个前缀码编码方案对应于一棵二叉树T。字符c在树T中的深度记为d T(c)。d T(c)也是字符c的前缀码长。则平均码长定义为： [1996] 设t 为一棵二叉树的根结点地址指针，试设计一个非递归算法完成把二叉树中每个结点的左右孩子位置交换。 int swithLRChild(BiTree *t) { BiTree *stack[100] = {0}; int stack_length = 0; if (NULL == t){ return 0; } stack[stack_length++] = t; while (stack_length > 0){ //pop stack BiTree *node = stack[stack_length - 1]; stack_length -= 1; BiTree *temp = node ->lchild; node->lchild = node ->rchild; node->rchild = temp; if (NULL != node ->rchild){ stack[stack_length++] = node ->rchild;} if (NULL != node ->lchild){ stack[stack_length++] = node ->lchild; } } return 1; } [1998]一棵高度为K 且有n个结点的二叉排序树，同时又是一棵完全二叉树存于向量t 中，试设计删除树中序号为i 且具有左右孩子的一个结点，而不使存储量增加保证仍为二叉排序树(不一定是完全二叉树)的算法。 //存数据的位置是从 1 的索引开始的，避免需要访问索引为0 的空间，避免需要频繁的索引 转换 void delNodeInSortedBiTree(int *sorted_bitree, int *last_index,int i) { //因为题目中描述具有左右孩子，所以直接从左孩子的最右边叶子节点开始//分两种情况，左孩子没有右孩子，那么左孩子之后的节点都移动一个位子//左孩子存在右孩子，则从右孩子的左孩子一直走，到叶子节点停止，因为是叶子节点//就不需要移动元素了 int del_node_index = 2*i; if (2*del_node_index + 1 >= *last_index) 淮海工学院计算机工程学院实验报告书 课程名：《算法分析与设计》 题目：实验3 贪心算法 哈夫曼编码 班级：软件102班 学号：11003215 姓名：鹿迅 实验3 贪心算法 实验目的和要求 （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用 （4）证明哈夫曼树满足最优子结构性质； （5）设计贪心算法求解哈夫曼编码方案； （6）设计测试数据，写出程序文档。 实验内容 设需要编码的字符集为{d 1, d 2, …, dn }，它们出现的频率为 {w 1, w 2, …, wn }，应用哈夫曼树构造最短的不等长编码方案。 实验环境 Turbo C 或VC++ 实验学时 2学时，必做实验 数据结构与算法 struct huffman { double weight; //用来存放各个结点的权值 int lchild,rchild,parent; //指向双亲、孩子结点的指针 }; 核心源代码 #include int min=11000; int min1; for(int k=0;k 二叉树的算法： 用扩展先序遍历序列创建二叉树； 递归遍历算法 中序非递归遍历层次遍历 二叉树深度的算法 实现代码如下： #include //以下为递归遍历算法 void PreOrder(BitTree root) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ { if (root!=NULL) { Visit(root ->data); /*访问根结点*/ PreOrder(root ->LChild); /*先序遍历左子树*/ PreOrder(root ->RChild); /*先序遍历右子树*/ } } void InOrder(BitTree root) /*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ { if (root!=NULL) { InOrder(root ->LChild); /*中序遍历左子树*/ Visit(root ->data); /*访问根结点*/ InOrder(root ->RChild); /*中序遍历右子树*/ } } void PostOrder(BitTree root) /* 后序遍历二叉树，root为指向二叉树(或某一子树)根结点的指针*/ { if(root!=NULL) { PostOrder(root ->LChild); /*后序遍历左子树*/ PostOrder(root ->RChild); /*后序遍历右子树*/ Visit(root ->data); /*访问根结点*/ } } //中序非递归遍历 void InOrder1(struct Node *head) { struct Node *p; struct Node *stack[20]; int top=0; p=head; while(p||top!=0) { while (p) 第六章树及二叉树 一、下面是有关二叉树的叙述，请判断正误 （√）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）2.二叉树中每个结点的两棵子树的高度差等于1。 （√）3.二叉树中每个结点的两棵子树是有序的。 （×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 （×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。（应当是二叉排序树的特点）（×）6.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1） （×）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （×）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。（应2i-1） （√）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子女结点的指针，还有n+1个空指针。）即有后继的指针仅n-1个。 （√）10.具有12个结点的完全二叉树有5个度为2的结点。 最快方法：用叶子数＝[n/2]＝6，再求n 2=n -1=5 (r ) 11、哈夫曼树中没有度为1的结点，所以必为满二叉树。 (r )12、在哈夫曼树中，权值最小的结点离根结点最近。 (r )13、线索二叉树是一种逻辑结构。 （√）14、深度为K的完全二叉树至少有2K-1个结点。 (√ )15、具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。 (√ )16、前序和中序遍历用线索树方式存储的二叉树，不必使用栈。 (╳ )17、哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。 二、填空 1．由３个结点所构成的二叉树有5种形态。 2. 一棵深度为6的满二叉树有n 1+n 2 =0+ n 2 = n -1=31 个分支结点和26-1 =32个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 3．一棵具有２５７个结点的完全二叉树，它的深度为9。 （注：用 log 2 (n) +1= 8.xx +1=9 4.设一棵完全二叉树有700个结点，则共有 350个叶子结点。 答：最快方法：用叶子数＝[n/2]＝350 5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有500个叶子结点，有499个度为2的结点，有1个结点只有非空左子树，有0个结点只有非空右子树。 二叉树三种遍历算法的源码 二叉树三种遍历算法的源码背诵版 本文给出二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法，直接用于考研答题。 1.先序遍历非递归算法 #define maxsize 100 typedef struct { Bitree Elem[maxsize]; int top; }SqStack; void PreOrderUnrec(Bitree t) { SqStack s; StackInit(s); p=t; while (p!=null || !StackEmpty(s)) { while (p!=null) //遍历左子树 { visite(p->data); push(s,p); p=p->lchild; }//endwhile if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历 { p=pop(s); p=p->rchild; }//endif }//endwhile }//PreOrderUnrec 2.中序遍历非递归算法 #define maxsize 100 typedef struct { Bitree Elem[maxsize]; int top; }SqStack; void InOrderUnrec(Bitree t) { SqStack s; StackInit(s); p=t; while (p!=null || !StackEmpty(s)) { while (p!=null) //遍历左子树 { push(s,p); p=p->lchild; }//endwhile if (!StackEmpty(s)) { p=pop(s); visite(p->data); //访问根结点 p=p->rchild; //通过下一次循环实现右子树遍历}//endif }//endwhile }//InOrderUnrec 3.后序遍历非递归算法 #define maxsize 100 typedef enum{L,R} tagtype; typedef struct { Bitree ptr; tagtype tag; }stacknode; typedef struct { stacknode Elem[maxsize]; int top; }SqStack; void PostOrderUnrec(Bitree t)创建一个二叉树并输出三种遍历结果
中衡算法分析与【设计明细】-实验二-哈夫曼编码
二叉树的各种算法
实验三.哈夫曼编码的贪心算法设计
数据结构C语言实现二叉树三种遍历
哈夫曼编码算法实现完整版
二叉树遍历算法的实现
哈夫曼树建立、哈夫曼编码算法的实现
二叉树的遍历算法实验报告
二叉树遍历C语言(递归,非递归)六种算法
二叉树的建立及几种简单的遍历方法
0023算法笔记——【贪心算法】哈夫曼编码问题
东北大学计算机初试历年二叉树算法题目及解答
哈夫曼编码_贪心算法
二叉树的各种遍历算法及其深度算法
数据结构第6章二叉树作业与答案教材
二叉树三种遍历算法代码_
- 二叉树的遍历 三遍历转化详解
- 二叉树遍历C语言(递归,非递归)六种算法
- 二叉树的建立及遍历算法的实现
- 数据结构C语言实现二叉树三种遍历
- 二叉树的各种算法
- 二叉树三种遍历算法代码_
- 数据结构C语言实现二叉树三种遍历
- 二叉树的三种遍历算法
- 递归非递归两种算法遍历二叉树
- 数据结构C语言实现二叉树三种遍历
- 用递归和非递归算法实现二叉树的三种遍历
- 二叉树地遍历算法
- 实现二叉树的各种遍历算法实验报告
- 二叉树前序、中序、后序三种遍历的非递归算法
- 数据结构C语言实现二叉树三种遍历(考试类别)
- 用程序生成如下二叉树,并输出三种遍历算法的遍历结果：
- 数据结构C语言实现二叉树三种遍历
- 数据结构二叉树的实现与三种遍历
- 二叉树的层次遍历算法
- 计算机考研408 数据结构算法总结及二叉树三种遍历算法的源码背诵版