实验十一二叉树的进一步操作.doc

《实验十一二叉树的进一步操作.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、个人收集整理勿做商业用途浙江大学城市学院实验报告课程名称　　　　　　数据结构基础　　　　　实验项目名称　实验十一二叉树的进一步操作　　　　学生姓名　　专业班级　　学号　实验成绩　　指导老师(签名)　日期20１４-1２-25一.实验目的和要求１、熟练掌握二叉树二叉链表的存储结构。2、进一步掌握在二叉链表上的二叉树操作的实现原理与方法。3、掌握中序遍历的非递归算法。二.实验内容１、实现以下说明的操作函数，添加到实验十所写的头文件binarｙ_ｔree.h中,并建立主函数文件tｅst4_2.cｐｐ，编写测试语句加以验证。操作函数如下：①ｖｏｉdＩnＯｒdｅr2(BT

2、reeNode　*BT　）;／/非递归中序遍历二叉树BT②voｉdＣhａngeＢＴｒee（BTrｅeNode*&ＢT);//将二叉树中的所有结点的左右子树进行交换:③InｔCounｔＢＴｒee(BTｒeeNoｄｅ＊BＴ);//统计二叉树中的所有结点数并返回④BＴreｅNoｄｅ*ＣopyＢTreｅ(BTｒｅｅＮoｄe*ＢT）;//复制一棵二叉树，并返回复制得到的二叉树根结点指针2、选做：实现以下说明的操作函数，添加到头文件ｂinarｙ_ｔreｅ．h中,并在主函数文件tｅst4_2.cpp中添加相应语句进行测试。①ｉntSimilａrＴrees(BTrｅeNodｅ

3、*ＢT1，BTｒeeNoｄｅ＊BＴ2）/／判断两棵二叉树是否相似。所谓相似是指如果两棵二叉树具有相同的树型,则称它们是相似的,否则不是。②BＴｒeeNｏde*RemovｅLeaｖes(BＴreｅＮoｄe*ＢT1)／／摘树叶:摘除一棵二叉树上的所有叶子结点后返回一棵新的二叉树。3、填写实验报告,实验报告文件取名为ｒeport11．doｃ。4、上传实验报告文件repｏrt１1.ｄｏc、源程序文件teｓt4_２．cpp及binａrｙ_tｒee.h到Ｆｔｐ服务器上自己的文件夹下。三.函数的功能说明及算法思路个人收集整理勿做商业用途（包括每个函数的功能说明，及一些重要函

4、数的算法实现思路)结构定义:二叉树:sｔruct　BTreeNode{ＥleｍTyｐe　daｔa;ﻩBＴreeＮｏｄe*lｃhilｄ;ﻩＢTreeＮode*rcｈｉld;｝;顺序栈:ｓｔｒuctStack｛BTreｅNｏde　＊*sｔack；　/／存栈元素inttop;inｔ　ＭａxSiｚe；}；Ｏperatiｏns:二叉树:　voidIniｔBTree（BTｒeeNoｄe＊&ＢＴ　)/／初始化二叉树BTvoiｄCreatｅBＴree(BＴreｅＮoｄe*＆BＴ，ｃｈａr*a)//根据字符串ａ所给出的广义表表示的二叉树建立二叉链表存储结构　ｖoidPｒintB

5、Tｒｅｅ（ＢＴrｅeNｏde＊BT　)//输出二叉树BT　　voｉｄ　CleaｒＢTreｅ(BTrｅeNode　*＆BT）//清除二叉树BTvoｉdIｎOrdｅr２(　BTreｅNｏdｅ*ＢT)//非递归中序遍历二叉树BTvoidChａngeＢTree(BTreeＮode　＊＆BT)/／将二叉树中的所有结点的左右子树进行交换　　int　CounｔBＴreｅ（BTreｅNodｅ*ＢＴ）//统计二叉树中的所有结点数并返回　BTreeNodｅ　*CopyBTree(ＢＴreｅNode*BT)／/复制一棵二叉树,并返回复制得到的二叉树根结点指针　inｔSｉmiｌaｒT

6、reｅs（BＴreeNode＊BＴ1,BTreeNｏｄe*BT2)//判断两棵二叉树是否相似。所谓相似是指如果两棵二叉树具有相同的树型,则称它们是相似的,否则不是。BＴｒeeNoｄe＊RｅmｏvｅＬeaｖｅs(BTreeNode　＊BT1)//摘树叶:摘除一棵二叉树上的所有叶子结点后返回一棵新的二叉树。顺序栈：vｏiｄInitSｔack(Stack＆S)/／初始化栈为空,把栈设置为空并完成栈空间的动态存储分配ｖoidPush(Stａck&S,BTreeNode＊iｔem)//元素ｉtｅm进栈,即插入到栈顶BTreeNode*Pop(Ｓtａck&S)//删除栈顶

7、元素并返回booｌEmptyStａck(Stacｋ&S)//判断S是否为空，若为空则返回tｒuｅ,否则返回ｆalsevoidＣleａｒSｔａck(Ｓtａck&S)//清除栈S中的所有元素,释放动态存储空间个人收集整理勿做商业用途ｅnd　GenerａｌTｒｅe算法:void　InOｒdｅr2(BＴrｅeNode*BT　)／/非递归中序遍历二叉树ＢＴ{　定义堆栈ｓﻩ定义树结点P　初始化栈s　　　wｈiｌe(p不为空或者s不为空)　　{ﻩif(p不为空)ﻩ将p进栈　;P的值重新赋为p的左孩子ﻩiｆ(s不为空)ﻩﻩ将出栈的值赋给ｐ;输出p的根的值　；P等于p的右边孩子

8、;　ﻩ}　}voiｄCｈangeBTr