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

浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验十一 二叉树的进一步操作 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1、熟练掌握二叉树二叉链表的存储结构。2、进一步掌握在二叉链表上的二叉树操作的实现原理与方法。3、掌握中序遍历的非递归算法。二. 实验内容1、实现以下说明的操作函数，添加到实验十所写的头文件binary_tree.h中，并建立主函数文件test4_2.cpp，编写测试语句加以验证。操作函数如下：void InOrder2( BTreeNode *BT ); /非递归中序遍历二叉树BT void ChangeBTree(BTreeNode *&BT);/将二叉树中的所有结点的左右子树进行交换：Int CountBTree(BTreeNode *BT);/统计二叉树中的所有结点数并返回BTreeNode * CopyBTree(BTreeNode *BT);/复制一棵二叉树，并返回复制得到的二叉树根结点指针2、选做：实现以下说明的操作函数，添加到头文件binary_tree.h中，并在主函数文件test4_2.cpp中添加相应语句进行测试。int SimilarTrees（BTreeNode *BT1，BTreeNode *BT2）/判断两棵二叉树是否相似。所谓相似是指如果两棵二叉树具有相同的树型，则称它们是相似的，否则不是。BTreeNode * RemoveLeaves（BTreeNode *BT1）/摘树叶：摘除一棵二叉树上的所有叶子结点后返回一棵新的二叉树。3、填写实验报告，实验报告文件取名为report11.doc。4、上传实验报告文件report11.doc 、源程序文件test4_2.cpp及binary_tree.h到Ftp服务器上自己的文件夹下。三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路）函数：void InOrder2( BTreeNode *BT )功能：非递归中序遍历二叉树BT思路：使用链栈来储存结点值。当前结点或者链栈非空时，判断当前结点是否非空，若非空则将其入栈，指针指向左孩子进入下一轮判断；若空则将栈顶元素（即当前结点的根结点）出栈输出，指针指向其右孩子进入下一轮判断。函数：BTreeNode* ChangeBTree(BTreeNode *BT)功能：将二叉树中的所有结点的左右子树进行交换思路：利用递归，优先交换最底层的结点。函数：int CountBTree(BTreeNode *BT)功能：统计二叉树中的所有结点数并返回思路：如果当前结点为空，则返回0；否则返回其左右孩子结点数之和加1函数：BTreeNode * CopyBTree(BTreeNode *BT)功能：复制一棵二叉树，并返回复制得到的二叉树根结点指针思路：如果当前结点为空则返回空，否则新建结点保存当前结点的值，并递归复制其左右孩子。函数（选作）：int SimilarTrees(BTreeNode *BT1,BTreeNode *BT2)功能：判断两棵二叉树是否相似思路：假如两棵树都为空，则相似返回1；若仅有一个非空，则不相似返回0；两个都不为空，返回递归分别比较以其左右孩子为根结点的子树是否相似。函数（选作）：BTreeNode * RemoveLeaves(BTreeNode *BT)功能：摘树叶：摘除一棵二叉树上的所有叶子结点后返回一棵新的二叉树思路：如果当前结点为空则返回空，否则则先判断是否为叶子结点（左右孩子均为空），若是则删除返回空，若不是，递归调用函数对其非空子树进行摘叶操作。四. 实验结果与分析（包括运行结果截图、结果分析等）测试数据：ab$cd$e$结果分析：非递归中序遍历结果为b a d c e，正确；该二叉树结点数为5，正确；经左右交换的二叉树和由原二叉树复制而来的二叉树输出均正确。选作部分测试数据：hi$jk$l$结果分析：该二叉树应当与第一次输入时的二叉树相似，经函数判断，该二叉树与复制的原二叉树相似，与经过左右交换的