二叉樹實驗報告-8

實驗報告課程數(shù)據(jù)結(jié)構(gòu)實驗名稱實驗六二叉樹學(xué)號姓名實驗日期：2012/12/17實驗六二叉樹實驗?zāi)康模?.熟悉二叉樹結(jié)點的結(jié)構(gòu)和對二樹的基本操作；2.熟練掌握二叉樹在二叉鏈表存儲結(jié)構(gòu)中的常用遍歷方法：先序遞歸遍歷、中序遞歸和非遞歸遍歷、后序遞歸遍歷；3.了解二叉樹的按層遍歷、先序非遞歸遍歷及后序遞歸遍歷；4.掌握哈夫曼樹的構(gòu)造方法及哈夫曼編碼。實驗原理：利用遞歸算法建立二叉樹；二叉鏈表存儲結(jié)構(gòu)中的常用遍歷方法：先序遞歸遍歷、中序遞歸和非遞歸遍歷、后序遞歸遍歷；哈夫曼樹的構(gòu)造方法及哈夫曼編碼。實驗內(nèi)容：7-23以例7-3為例，編寫一個程序：首先，建立如圖7-20（a）所示不帶頭結(jié)點的二叉樹；然后，中序線索化該二叉樹；最后，用循環(huán)結(jié)構(gòu)輸出該中序線索化二叉樹各結(jié)點的序列信息。7-24哈夫曼編碼的程序設(shè)計。要進行哈夫曼編碼的字符集為｛A，B，C，D｝，各字符在電文中出現(xiàn)的次數(shù)集為｛1，3，5，7｝。要求：（1）編寫實現(xiàn)哈夫曼樹構(gòu)造和哈夫曼編碼的函數(shù)；（2）給出程序運行結(jié)果；（3）畫出類似圖7-17的哈夫曼樹構(gòu)造過程。實驗結(jié)果：7-23（1）建立頭文件InThread.h如下：typedefstructNode{DataTypedata;/*數(shù)據(jù)元素*/intleftThread;/*左線索*/structNode*leftChild;/*左指針*/structNode*rightChild;/*右指針*/intrightThread;/*右線索*/}ThreadBiNode;/*===================================*//*把一顆二叉樹進行中序線索化的函數(shù)為CreatInThread()，*//*該函數(shù)把頭結(jié)點進行了中序線索化，其余部分的中序線索化*//*是通過調(diào)用InThread()函數(shù)實現(xiàn)的。InThread()是一個遞歸*//*函數(shù)。*//*===================================*/voidInThread(ThreadBiNode*current,ThreadBiNode**pre)/*中序線索化二叉樹*//*current為當(dāng)前結(jié)點的指針，pre為當(dāng)前結(jié)點的中序前驅(qū)結(jié)點指針*/{if(current!=NULL){InThread(current->leftChild,pre);/*中序線索化左子樹*/if(current->leftChild==NULL){current->leftThread=1;/*建立左線索標(biāo)記*/current->leftChild=*pre;/*建立左線索指針*/}elsecurrent->leftThread=0;if(current->rightChild!=NULL)current->rightThread=0;elsecurrent->rightThread=1;if((*pre)->rightChild==NULL){(*pre)->rightThread=1;/*建立右線索標(biāo)記*/(*pre)->rightChild=current;/*建立右線索指針*/}elsecurrent->rightThread=0;*pre=current;/*前序結(jié)點指針等于當(dāng)前結(jié)點指針*/InThread(current->rightChild,pre);/*中序線索化右子樹*/}}/*============================*//*創(chuàng)建中序線索化二叉樹*//*============================*/voidCreatInThread(ThreadBiNode**root)/*創(chuàng)建中序線索化二叉樹tree*/{ThreadBiNode*t=*root;/*保存原二叉樹根結(jié)點指針*/ThreadBiNode*current,*pre=*root;/*建立頭結(jié)點*/*root=(ThreadBiNode*)malloc(sizeof(ThreadBiNode));if(t==NULL)/*當(dāng)二叉樹為空時*/{(*root)->leftThread=0;(*root)->rightThread=1;(*root)->leftChild=*root;(*root)->rightChild=*root;}else/*當(dāng)二叉樹為非空時*/{current=t;(*root)->leftChild=t;/*置頭結(jié)點左指針*/(*root)->leftThread=0;/*置頭結(jié)點的左線索*/InThread(current,&pre);/*線索化二叉樹*/pre->rightChild=*root;/*置最后一個結(jié)點的右指針*/pre->rightThread=1;/*置最后一個結(jié)點的右線索*/(*root)->rightChild=pre;/*置頭結(jié)點的右指針*/(*root)->rightThread=1;/*置頭結(jié)點的右線索*/}}typedefstruct{ThreadBiNode*root;/*頭指針*/ThreadBiNode*current;/*當(dāng)前結(jié)點指針*/intnextComplete;/*遍歷結(jié)束標(biāo)記*/}ThreadBiTree;/*============================*//*初始化中序線索二叉樹*//*============================*/voidThreadInitiate(ThreadBiTree*tree,ThreadBiNode*root)/*初始化中序線索二叉樹*/{tree->root=root;tree->current=root;if(root==NULL)tree->nextComplete=1;elsetree->nextComplete=0;}/*============================*//*使中序線索二叉樹tree的當(dāng)前結(jié)點指針指向中序遍歷的第一個結(jié)點*//*============================*/voidFirst(ThreadBiTree*tree)/*使中序線索二叉樹tree的當(dāng)前結(jié)點指針指向中序遍歷的第一個結(jié)點*/{tree->current=tree->root;while(tree->current->leftThread==0)tree->current=tree->current->leftChild;if(tree->current==tree->root)tree->nextComplete=1;elsetree->nextComplete=0;}/*============================*//*使中序線索二叉樹tree的當(dāng)前結(jié)點指針指向中序遍歷的下一個結(jié)點*//*============================*/voidNext(ThreadBiTree*tree)/*使中序線索二叉樹tree的當(dāng)前結(jié)點指針指向中序遍歷的下一個結(jié)點*/{ThreadBiNode*p=tree->current->rightChild;if(tree->nextComplete==1)return;if(tree->current->rightThread==0)while(p->leftThread==0)p=p->leftChild;tree->current=p;if(tree->current==tree->root)tree->nextComplete=1;}/*============================*//*判斷是否已到中序線索二叉樹尾部函數(shù)*//*============================*/intEndOfNext(ThreadBiTree*tree)/*如中序線索二叉樹tree的nextComplete域值等于1，則表示已到尾部*/{returntree->nextComplete;}（2）建立主函數(shù)程序為：#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedefcharDataType;#include"InThread.h"ThreadBiNode*GetTreeNode(DataTypeitem,ThreadBiNode*left,ThreadBiNode*right){ThreadBiNode*p;p=(ThreadBiNode*)malloc(sizeof(ThreadBiNode));p->data=item;p->leftChild=left;p->rightChild=right;returnp;}voidMakeCharTree(ThreadBiNode**root){ThreadBiNode*b,*c,*d,*e,*f,*g,*h;g=GetTreeNode('G',NULL,NULL);d=GetTreeNode('D',NULL,NULL);e=GetTreeNode('E',g,NULL);b=GetTreeNode('B',d,e);h=GetTreeNode('H',NULL,NULL);f=GetTreeNode('F',NULL,h);c=GetTreeNode('C',f,NULL);*root=GetTreeNode('A',b,c);}voidmain(void){ThreadBiNode*root;ThreadBiTreetree;MakeCharTree(&root);CreatInThread(&root);printf("Binarytreetraversesequenceinorderis:");ThreadInitiate(&tree,root);for(First(&tree);!EndOfNext(&tree);Next(&tree))printf("%c",tree.current->data);printf("\n");printf("Thisprogramismadeby10273206!\n");}運行結(jié)果為：7-24（1）建立頭文件Haffman.h如下：哈夫曼樹的構(gòu)造：typedefstruct{intweight;intflag;intparent;intleftChild;intrightChild;}HaffNode;typedefstruct{intbit[MaxN];intstart;intweight;}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;}for(i=0;i<n-1;i++){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&&haffTree[j].flag==0){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;}}哈夫曼編碼的函數(shù)：voidHaffmanCode(HaffNodehaffTree[],intn,CodehaffCode[]){ Code*cd=(Code*)malloc(sizeof(Code));inti,j,child,parent;for(i=0;i<n;i++){cd->start=n-1;cd->weight=haffTree[i].weight;child=i;parent=haffTree[i].parent;while(parent!=-1){if(haffTree[parent].leftChild==child)cd->bit[cd->start]=0;elsecd->bit[cd->start]=1;cd->start--;child=parent;parent=haffTree[child].parent;}for(j=cd->start+1;j<n;j++)haffCode[i].bit[j]=cd->bit[j];haffCode[i].start=cd->start+1;haffCode[i].weight=cd->weight;}}（2）運行的程序：#include<stdio.h>#include<stdlib.h>#defineMaxValue10000#defineMaxBit10#defineMaxN100#include"Haffman.h"voidmain(void){