《数据结构》课件第5章 (2).ppt

【实现思路】根据提示输入字符型数据创建二叉树，输入值为所有字符型数据，输出为遍历后的每个结点的值的顺序。为了表示结点和结点之间的关系，输入的内容包括结点对应的编号和值。【实现过程】#includestdio.h#includemalloc.h#defineDatatypechar#include二叉树.c //二叉树.c参见实例5-1//Bitree二叉链表结构，参见结构5-2二叉树的链式存储voidinorder(Bitree*bt){ //中序遍历二叉树btif(bt!=NULL){inorder(bt-lchild); //中序递归遍历bt的左子树printf(＂%c＂，bt-data); //访问结点的数据域inorder(bt-rchild); //中序递归遍历bt的右子树}}voidinorder_notrecursive(Bitree*bt) //中序遍历二叉树(非递归算法){Bitree*q,*s[20];inttop=0;intbool=1;q=bt;do{while(q!=NULL){top++;s[top]=q;q=q-lchild;}if(top==0)bool=0;else{q=s[top]; top--; printf(%c,q-data);q=q-rchild;}}while(bool);}main(){Bitree*bt;charch;inti;bt=createbt();i=1;while(i){printf(\n中序遍历二叉树(递归按y键，非递归按n键):);fflush(stdin);scanf(%c,ch);if(ch==y)inorder(bt);elseinorder_notrecursive(bt);printf(\n);printf(\n继续操作吗?(继续按1键，结束按0键):);fflush(stdin);scanf(%d,i);}}二、哈夫曼算法实现【实训目的】理解并熟悉掌握构造哈夫曼树的算法，利用哈夫曼树进行编码。【实训内容】创建哈夫曼树和实现哈夫曼编码。【实现思路】根据提示输入结点的个数及各结点的权值，构造哈夫曼树并得到相应的哈夫曼编码。如果输入结点数为6，权值分别为2，4，6，8，9，12，则可得到如下哈夫曼编码：2shaffmancodeis11104shaffmancodeis01106shaffmancodeis1108shaffmancodeis119shaffmancodeis0112shaffmancodeis10【实现过程】#definemaxlen100typedefstruct{intweight;intlchild;intrchild;intparent;}Htnode; //二叉树结点结构typedefHtnodeht[maxlen];intn;voidInitht(htt){inti;puts(Howmanynodes?);scanf(%d,n);for(i=0;i2*n-1;i++){t[i].weight=0;t[i].parent=-1;t[i].lchild=-1;t[i].rchild=-1;}}voidInputweight(htt)//输入权值{intw;inti;for(i=0;in;i++){puts(EnterNextWeight);scanf(%d,w);t[i].weight=w;}}voidGetmin(htt,inti,int*p1,int*p2){longm1=999999;long