数据结构试验三

1、甘肃政法学院本科生实验报告（三）姓名: 学院: 专业: 班级: 实验课程名称 : 数据结构 实验日期 :2012 年 11 月 19 日 指导教师及职称 : 金涛 实验成绩 :开课时间： 2012-2013 学年 第一 学期甘肃政法学院实验管理中心印制实验题目树和二叉树小组合作否姓名班级学号一、实验目的1.掌握树的相关概念，包括树、结点的度、树的度、分支结点、叶子结点、儿子 结点、双亲结点、树的深度、森林等定义；2.掌握树的表示,包括树形表示法、文氏图表示法、凹入表示法和括号表示法等；3.掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义；4.掌握二叉树的性质；5.重点掌握二叉树的存储结

2、构，包括二叉树顺序存储结构和链式存储结构；6.重点掌握二叉树的基本运算和各种遍历算法的实现；7.掌握线索二叉树的概念和相关算法的实现；8.掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法；9.最后灵活运用二叉树这种数据结构解决一些实际综合应用问题。二.实验环境一台装有 Microsoft Visual C+ 6.0的计算机。三、实验内容与步骤一、有关树的实验：1.树的形式化定义：树：T=K,R。K是包含n个结点的有穷集合(n0),关系R满足以下条件：(1)有且仅有一个结点k0K,它对于关系R来说没有前驱结点，结点k0称作树 的根。(2)除结点k0外,K中的每个结点对于关系R来说都有且

3、仅有一个前驱结点。(3) K中每个结点对于关系R来说可以有多个后继结点。2.树的递归定义：树是由n(n0)个结点组成的有限集合(记为T)。其中，如果n=0,它是一棵空树，这是树的特例；如果n0,这n个结点中存在(有仅存在)一个结点作为树的根结点，简称为根(root),其余结点可分为m (m0)个互不相交的有限集T1,T2,Tm,其中每一 棵子集本身又是一棵符合本定义的树，称为根root的子树。3.树的性质：性质1树中的结点数等于所有结点的度数加1。性质2度为m的树中第i层上至多有mi-1个结点,这里应有i1。性质3具有n个结点的m次树的最小高度为logm(n(m-1)+1)。例：设计一个算法，

4、输出所有叶子结点：程序运行过程如下：运行结果如下:二、有关二叉树的实验：1.二叉树概念二叉树也称为二次树或二分树，它是有限的结点集合，这个集合或者是空，或者 由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。二叉树的 定义是一种递归定义。2.二叉树性质：性质1非空二叉树上叶结点数等于双分支结点数加1。性质2对完全二叉树中编号为i的结点(1i1,n为结点数)有： 若in/2 ,即2i0)结点的完全二叉树的高度为Iog2n+1或Iog2n +1。1假设二叉树采用二叉链存储结构，设计一个算法求二叉树中结点值为x的节 点的层数：程序运行过程如下：FlFLS割j l实凶IiiVir t Pr

5、jj*c L IhjjiH工w：工itJDA世以”適J 0-illylubbl meiiibitir Lev elInclLMlloiibl_ree.cpp,int LemeitEivHiDide當n.EleiM卵c* xvlnt h)lit 1;iF (b-WLLreturn(EH):else IF(D-dataK) rtuirn(hj ；else1-Lewlclcriild,M,h*n； if (i*-0)return(1);丄占色return(Lvv (b- rc hlldpx,h*1);BTHtide *b;liU h；EWFppr* x;inriparpQ!rHnde(h .MfUf

6、DC ,G )fC(E F J ) ；prdntf (li =M;DispfiTHade (b) ;printff (BSn1B);prirlfCAJili -11ufKhniil) iif (hijiprintf(h中不袪诒点；elseprlntFCfe中1瞬点的惑MtdXn.x.h)：111exam/ V .eicf U errnr(S)p0 drriiingtsji运行结果如下:*C: Eocu*ent s and SettingsAdinistratcrJ面数据结构获程一源程序谪丁拿V h = ftBD.Cstruct snodBBTbkid 4nni|p; int prpnt; qu

7、MKSizeJ;BTMDdtt q ； int Frontar*4rap ；Front-rpar-1;rear+*;(iirrorapjrenitK,1;uhilt(frcnitlCbtld*HlllLlp-1-ronlL iurii止0 (quipJ. pai entf- 1 printf(tc-aapqup鼻W町;priiitKXtMi i怕山爲)；red*;qurpdr -nnrir -q-1 chi 1 d; qu(rear,pdrntfront运行结果如下:米用算法实现先序、中序、后序的递归方法:程序运行过程如下:嚮SSBISJ中軸住置/ 定加乍环起帧专ICIatisV iFiltV

8、iew小If rchilcl*-HULIL)E 吨啓有右孫子时将其逬刽Vif (b!-HUI L)vuid IiiOnJurCBTHudL *bif(hl-HUI I)inDrdPK(b-Mchiltl): prinLFCc -AildUQ： ltiDrdr(bOrihild);Ptarijurfb-lclilliiK FVEIO r der(b-rc liild); printFCltc,Bpb-dU):釘t*id *b;EFHtHTHllle(k,i(R( ,S)JfCErF) )；priHtFO：-; I1 & pBTNtfe (b); pr lntf (n;printFCjT历

9、年列；)jPreOrderfh);prints(Sn-); prinkFC屯序通崩顷； J nDrder(b ;prin11(nJ ;print就百便通去梓列:):Posturdft-Cb) sprint!t AnMj;: CliMmV Fil理iEWId rrar(, ll ijKirning(兮运行结果如下:江CiVDocuicnts and SettingsVAdiiristrator臬両谶据舞构載程一源程序第 7 軾哈夫曼编码设计实验:程序运行过程如下:12 iLe工山匕JLitfi Insert ij$j telIdD1 tmdaT总士金麻 pr | U *(0 固铛%|3 *Glu

10、bulc(AJl global mymbertj*|lPreOrderI习电prlnclude btrp.cpp-uuidPreQrdertBlHiiLl? *n)* S ituiuiJcr clatcetprintFCcaata);PreOrd;PrpOrdpr(lj-rchild)-f 側问 ffl 结点时隹;霍需棘:;void POStDrder(BTHodlf *D)八百序通历的锻归旱注Wre匚ildid? r1.* kt1/Inode初l-nnH窝眾1U； fl氏个珀点氐三*只 jiM 滋造二胃捌锂冑氢中餓肝11 (ht|E.wel*itCnin1)tlwIf tMhLwlghtLn

11、!)* rrr(rU(htk).pjrpnt1cliarciH)；Llit SUrt； )HC4i1r;ijuid Crri?teMT(IITHadPht|Tintn)cltar ddtafC;wJuht ；卩irfnt;lcriiid rhiid;ijkFlnfiflc-FrniDdp：ruM.nin?;(i-B-i结盍的相关戟賢初值 F#litil j .pareftt-ht 1 j. lldldl-liil: 1J .rchlld- 1:；!*tnl inr int:Int )IITHaa#;切回輯struet车蒔结点町ClwtfM.rFilcViewltinclud# (stdifi

12、.binclude Strimg hy利leHtw N 5BBHiike II ?*- i 5幘|阡rrijct3 .11 u.i Ust% zui 1t-mll l*di bak% jjJ-ytl duai 土山|亠 A g 圏普彌勺封H Jhi.,1|A9I dHi fFH*mlit!fii| *.hi 1n idata); /*PreOrder(b-lchild);PreOrder(b-rchild); void In Order(BTNode *b) if (b!=NULL)In Order(b-lchild);prin tf(%c ,b-data); /*In Order(b-rch

13、ild); void PostOrder(BTNode *b) /*if (b!=NULL) PostOrder(b-lchild);PostOrder(b-rchild); printf(%c ,b-data); /*层次遍历其过程是：先序遍历的递归算法*/访问根结点*/*中序遍历的递归算法*/访问根结点*/后序遍历递归算法*/访问根结点*/由先序遍历的定义可知，其递归模型f（）如下:f(p):不做任何事件若p=NULLf(p):输出*p结点的data域值；其他情况f(p-lchild);f(p-rchild);void PreOrder1(BTNode *b) BTNode *p;stru

14、ct BTNode *pt;int tag;1:未访问，0:可访问 StMaxSize;int top=-1;top+;Sttop.pt=b;Sttop.tag=1;while (top-1)/栈不空时循环 if (Sttop.tag=1)/不能直接访问的情况p=Sttop.pt;top-;if (p!=NULL)(2)式 top+;/右孩子结点进栈Sttop.pt=p-rchild;Sttop.tag=1;top+;/左孩子结点进栈Sttop.pt=p-lchild;Sttop.tag=1;top+;/根结点进栈Sttop.pt=p;Sttop.tag=0; /end of if (Stto

15、p.tag=1)prin tf(%c ,Sttop.pt-data);top-; /while（2）第二种方法（常规方法）void PreOrder2(BTNode *b) BTNode *StMaxSize,*p; int top=-1;top+; Sttop=b; /根结点入栈while (top-1)/栈不为空时循环 p=Sttop; top-; /退栈并访问该结点prin tf(%c ,p-data);if (p-rchild!=NULL) /右孩子结点入栈 top+; Sttop=p-rchild; if (p-lchild!=NULL)/ top+; Sttop=p-lchild;

16、 2）中序遍历非递归算法第二种方法（常规方法） 由中序遍历过程可知，采用一个栈保存需要返回的结点指针，先扫描（并非访 问）根结点的所有左结点并将它们一一进栈。然后出栈一个结点，显然该结if (Sttop.tag=0)/直接访问的情况左孩子结点入栈点 没有左孩子结点或者左孩子结点已访问过（进一步说明该结点的左子树均已访 问），则访问它。 然后扫描该结点的右孩子结点， 将其进栈， 再扫描该右孩子结 点的所有左结点并 进栈，如此这样，直到栈空为止。3)后序遍历非递归算法：第二种方法(常规方法)由后遍历过程可知，采用一个栈保存需要返回的结点指针，先扫描根结点的所 有左结点并-进栈，出栈一个结点*b即当

17、前结点，然后扫描该结点的右孩子结点并入栈，再扫描该右孩子结点的所有左结点并入栈。当一个结点的左右孩 子结点均访问后再访问该结点，如此这样，直到栈空为止。8.二叉树的基本运算：创建二叉树CreateBTNode(*b,*str):根据二叉树括号表示法的字符串*str生成对应的链式存储结构。查找结点FindNode(*b,x):在二叉树b中寻找data域值为x的结点,并返回 指向该结点的指针。找孩子结点LchildNode(p)和RchildNode(p):分别求二叉树中结点*p的左 孩子结点和右孩子结点。求高度BTNodeDepth(*b):求二叉树b的高度。若二叉树为空,则其高度为0；否则,其

18、高度等于左子树与右子树中的最大高度加l。输出二叉树DispBTNode(*b):以括号表示法输出一棵二叉树。9.哈夫曼树1)为了实现构造哈夫曼树的算法，设计哈夫曼树中每个结点类型如下:具体构造方法如下： 设需要编码的字符集合为d1,d2,dn,各个字符在电文 中出现的次数集合为w1,w2,wn,以d1,d2,d n作为叶结点，以w1,w2,wn作为各根结点到每个叶结点的权值构造一棵二叉树,规定哈夫曼树中的左分支为0,右分支为1,则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。typedef struct char data; floatweight; int parent;int lchild;int rchild; HTNode;2）哈夫曼编码:/*结点值*/*权重*/*双亲结点*/*左孩子结点*/*右孩子结点*/为了实现构造哈夫曼编码的算法，设计存放每个结点哈夫曼编码的类型如下:typedef structchar cdN; /*存放当前结点的哈夫曼码*/int start; /*存放哈夫曼码在cd中的起始位置*/ HCode;10.任何n(n0)个不同结点的二叉树，都可由它的中序序列