实验11 二叉树进一步操作

《实验11 二叉树进一步操作》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验十一二叉树的进一步操作实验成绩指导老师（签名）日期一.实验目的和要求1、熟练掌握二叉树二叉链表的存储结构。2、进一步掌握在二叉链表上的二叉树操作的实现原理与方法。3、掌握中序遍历的非递归算法。二.实验内容1、实现以下说明的操作函数，添加到实验十所写的头文件binary_tree.h中，并建立主函数文件test4_2.cpp，编写测试语句加以验证。操作函数如下：①voidInOrder2(BTreeNode*BT);//非递归中序遍历二叉树BT②voidCha

2、ngeBTree(BTreeNode*&BT);//将二叉树中的所有结点的左右子树进行交换：③IntCountBTree(BTreeNode*BT);//统计二叉树中的所有结点数并返回④BTreeNode*CopyBTree(BTreeNode*BT);//复制一棵二叉树，并返回复制得到的二叉树根结点指针2、选做：实现以下说明的操作函数，添加到头文件binary_tree.h中，并在主函数文件test4_2.cpp中添加相应语句进行测试。①intSimilarTrees（BTreeNode*BT1，BTreeNode

3、*BT2）//判断两棵二叉树是否相似。所谓相似是指如果两棵二叉树具有相同的树型，则称它们是相似的，否则不是。②BTreeNode*RemoveLeaves（BTreeNode*BT1）//摘树叶：摘除一棵二叉树上的所有叶子结点后返回一棵新的二叉树。3、填写实验报告，实验报告文件取名为report11.doc。4、上传实验报告文件report11.doc、源程序文件test4_2.cpp及binary_tree.h到Ftp服务器上自己的文件夹下。三.函数的功能说明及算法思路（包括每个函数的功能说明，及一些重要函数的算法

4、实现思路）函数：voidInOrder2(BTreeNode*BT)功能：非递归中序遍历二叉树BT思路：使用链栈来储存结点值。当前结点或者链栈非空时，判断当前结点是否非空，若非空则将其入栈，指针指向左孩子进入下一轮判断；若空则将栈顶元素（即当前结点的根结点）出栈输出，指针指向其右孩子进入下一轮判断。函数：BTreeNode*ChangeBTree(BTreeNode*BT)功能：将二叉树中的所有结点的左右子树进行交换思路：利用递归，优先交换最底层的结点。函数：intCountBTree(BTreeNode*BT)功能

5、：统计二叉树中的所有结点数并返回思路：如果当前结点为空，则返回0；否则返回其左右孩子结点数之和加1函数：BTreeNode*CopyBTree(BTreeNode*BT)功能：复制一棵二叉树，并返回复制得到的二叉树根结点指针思路：如果当前结点为空则返回空，否则新建结点保存当前结点的值，并递归复制其左右孩子。函数（选作）：intSimilarTrees(BTreeNode*BT1,BTreeNode*BT2)功能：判断两棵二叉树是否相似思路：假如两棵树都为空，则相似返回1；若仅有一个非空，则不相似返回0；两个都不为空，

6、返回递归分别比较以其左右孩子为根结点的子树是否相似。函数（选作）：BTreeNode*RemoveLeaves(BTreeNode*BT)功能：摘树叶：摘除一棵二叉树上的所有叶子结点后返回一棵新的二叉树思路：如果当前结点为空则返回空，否则则先判断是否为叶子结点（左右孩子均为空），若是则删除返回空，若不是，递归调用函数对其非空子树进行摘叶操作。四.实验结果与分析（包括运行结果截图、结果分析等）测试数据：ab$$cd$$e$$结果分析：非递归中序遍历结果为badce，正确；该二叉树结点数为5，正确；经左右交换的二叉树和由

7、原二叉树复制而来的二叉树输出均正确。选作部分测试数据：hi$$jk$$l$$结果分析：该二叉树应当与第一次输入时的二叉树相似，经函数判断，该二叉树与复制的原二叉树相似，与经过左右交换的二叉树不相似，正确；经过摘叶操作后，只剩下原本有孩子的h和j接点，正确。五.心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）【附录----源程序】