数据结构实验三

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) 有且仅有一个结点k0 K,它对于关系R来说没有前驱结点，结点k0称作树 的根。(2) 除结点k0外,K中的每

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

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

5、过程如下：Fl Fls 割j l 实凶 IiiVir t Pr jj*c L IhjjiH 工w：工itJda 世以”適J 0-ill ylubbl meiiibitir Lev elI”Workup ft im? pifiim? 9:InclLMllo iibl_ree.cpp,int LemeitEivHiDide 當n.EleiM卵c* xvlnt h)lit 1;iF (b-WLL ret urn (EH):else If (D-dataK) rtuirn(hj ；else1-L ewl clcriild,M,h*n； if (i*-0)return(1);丄占色return(Lvv

6、(b- rc hlld p x,h*1);BTHtide *b;liU h；EWFppr* x;inriparpQ!rHnde(h .MfUfDC ,G ) f C(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) p 0 drriiingtsji运行结果如下:*C: Eocu*ent s and SettingsA

7、dinistratcrJ面数据结构获程一源程序谪丁拿V h = ftBD.Cstruct snodBBTbkid 4nni|p; int prpnt; quMKSizeJ;BTMDdtt q； int Frontar*4rap； Front-rpar-1;rear+*;(iirror ap jrenitK,1; uhilt (frcnitlCbtld*HlllLl:嚮SSBISj中軸住置/ 定加乍环起帧专p-1-ronlL iurii止0 (quipJ. pai entf- 1 printf(tc-aapqup鼻W町;red*;ICIatisV iFiltView小If rchilcl*-HU

8、LIL)E吨啓有右孫子时将其逬刽Vqurpdr -nnrir -q-1 chi 1 d; qu(rear,pdrntfront运行结果如下:米用算法实现先序、中序、后序的递归方法:程序运行过程如下:12 iLe 工山匕 JLitfi Insert ij$j telId d1 tmdaT 总士金麻pr | U *(0固铛%|3 *Glubulc(AJl global mymbertj*|lPreOrderI习电prlnclude btrp.cpp - uuid PreQrdertBlHiiLl? *n)* S ituiuiJcr clatcetprintFCc aata); PreOrd;Prp

9、Ordpr(lj-rchild)-f側问ffl结点时 隹;霍需棘:;if (b!-HUI L)vuid IiiOnJurCBTHudL *bif (hl-HUI I)inDrdPK(b-Mchiltl): prinLFCc -AildUQ： ltiDrdr(bOrihild);void POStDrder(BTHodlf *D)八百序通历的锻归旱注WPtarijurfb-lclilliiK FveIO r der(b-rc liild); printFCltc ,Bpb-dU):釘t*id *b;EFHtHTHllle(k,i(R( ,S)JfCErF) )；priHtFO：-; I1 & p

10、BTNtfe (b); pr lntf ( n; printFCjT历年列；)jPreOrderfh); prints(Sn-); prinkFC屯序通崩顷； J nDrder(b ;prin11(nJ ;print就百便通去梓列:):Posturdft-Cb) sprint!t AnMj;re 匚 ildid? r1 .* kt: CliMmV Fil 理 iEWId rrar(, ll ijKirning (兮运行结果如下:江CiVDocuicnts and SettingsVAdiiristrator臬両谶据舞构載程一源程序第7軾哈夫曼编码设计实验:程序运行过程如下:1/Inode初l-

11、nnH窝眾1U； fl氏个珀点氐三*只jiM滋造二胃捌锂冑氢中餓肝11 (ht|E.wel*itCnin1)tlw If tMhLwlghtLn!)* rrr(rU (htk).pjrpnt1cliar ciH)； Llit SUrt； )HC4i1r; ijuid Crri?teMT(IITHadP ht|Tint n)cltar ddtafC; wJuht ； 卩irfnt; lcriiid r hiid;ijkFlnfiflc-FrniDdp：ruM.nin?;(i-B-i结盍的相关戟賢初值F#litil j .pareftt-ht 1 j. lldldl-liil: 1J .rchll

12、d- 1:；!*tnl inr int:Int )IITHaa#; 切回輯s truet车蒔结点町ClwtfM.rFilcViewltinclud# (stdifi .b include Strimg hy 利leHtw N 5B BHiike II ?*- i 5幘|阡rrijct3 .11 u.i Ust% zui 1t-mll l*di bak% jjJ-ytl dua i 土山|亠A g圏普彌勺封H Jhi.,1|A9I dHi fFH*mlit!fii| * hi 1 n idata); /* PreOrder(b-lchild); PreOrder(b-rchild); void

13、In Order(BTNode *b) if (b!=NULL)In Order(b-lchild);prin tf(%c ,b-data); /* In Order(b-rchild); void PostOrder(BTNode *b) /*if (b!=NULL) PostOrder(b-lchild); PostOrder(b-rchild); prin tf(%c ,b-data); /*层次遍历其过程是：先序遍历的递归算法*/访问根结点*/*中序遍历的递归算法*/访问根结点*/后序遍历递归算法*/访问根结点*/若二叉树非空（假设其高度为h）,贝（1）访问根结点（第1层）；（2）从左

14、到 右访问第2层的所有结点；（3）从左到右访问第3层的所有结点、第h层 的所有结点。7. 二叉树遍历非递归算法：先序遍历非递归算法（1）第一种方法：由先序遍历的定义可知，其递归模型f（）如下:f(p):不做任何事件若p=NULLf(p):输出*p结点的data域值；其他情况f(p-lchild);f(p-rchild);void PreOrder1(BTNode *b) BTNode *p;struct BTNode *pt;int tag; 1:未访问，0:可访问 StMaxSize;int top=-1;top+;Sttop.pt=b;Sttop.tag=1;while (top-1)/栈

15、不空时循环 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 (Sttop.tag=1)if (Sttop.tag=0)/直接访问的情况prin tf(%c ,Sttop.pt-data);top-; /while（2）第二种方法（常规方法）void PreOrder

16、2(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; 2）中序遍历非递归算法第二种方法（常规方法） 由中序遍历过程可知，采用一个栈保存需要返回的结点指针，先扫描（并非访 问）根结点的所有

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

18、ode(*b,*str):根据二叉树括号表示法的字符串 *str 生成对应的链式存储结构。查找结点FindNode(*b,x):在二叉树b中寻找data域值为x的结点,并返回 指向该结点的指针。找孩子结点LchildNode(p)和RchildNode(p):分别求二叉树中结点*p的左 孩子结点和右孩子结点。求高度BTNodeDepth(*b):求二叉树b的高度。若二叉树为空,则其高度为0 ； 否则,其高度等于左子树与右子树中的最大高度加l。输出二叉树DispBTNode(*b):以括号表示法输出一棵二叉树。9. 哈夫曼树1 )为了实现构造哈夫曼树的算法，设计哈夫曼树中每个结点类型如下:typ

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