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

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

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

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

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

4、功能说明及算法思路（包括每个函数的功能说明，及一些重要函数的算法实现思路）结构定义：二叉树：structBTreeNode{ElemTypedata;BTreeNode*lchild;BTreeNode*rchild;};顺序栈：structStack{BTreeNode**stack;//存栈元素inttop;intMaxSize;};Operations:二叉树：voidInitBTree(BTreeNode*&BT)//初始化二叉树BTvoidCreateBTree(BTreeNode*&BT,char

5、*a)//根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构voidPrintBTree(BTreeNode*BT)//输出二叉树BTvoidClearBTree(BTreeNode*&BT)//清除二叉树BTvoidInOrder2(BTreeNode*BT)//非递归中序遍历二叉树BTvoidChangeBTree(BTreeNode*&BT)//将二叉树中的所有结点的左右子树进行交换intCountBTree(BTreeNode*BT)//统计二叉树中的所有结点数并返回BTreeNode*Cop

6、yBTree(BTreeNode*BT)//复制一棵二叉树，并返回复制得到的二叉树根结点指针intSimilarTrees(BTreeNode*BT1,BTreeNode*BT2)//判断两棵二叉树是否相似。所谓相似是指如果两棵二叉树具有相同的树型，则称它们是相似的，否则不是。BTreeNode*RemoveLeaves(BTreeNode*BT1)//摘树叶：摘除一棵二叉树上的所有叶子结点后返回一棵新的二叉树。顺序栈：voidInitStack(Stack&S)//初始化栈为空，把栈设置为空并完成栈空间的动

7、态存储分配voidPush(Stack&S,BTreeNode*item)//元素item进栈，即插入到栈顶BTreeNode*Pop(Stack&S)//删除栈顶元素并返回boolEmptyStack(Stack&S)//判断S是否为空，若为空则返回true，否则返回falsevoidClearStack(Stack&S)//清除栈S中的所有元素，释放动态存储空间endGeneralTree算法:voidInOrder2(BTreeNode*BT)//非递归中序遍历二叉树BT{定义堆栈s定义树结点P初始化栈

8、swhile(p不为空或者s不为空){if(p不为空)将p进栈；P的值重新赋为p的左孩子if(s不为空)将出栈的值赋给p；输出p的根的值；P等于p的右边孩子；}}voidChangeBTree(BTreeNode*&BT){//将二叉树中的所有结点的左右子树进行交换定义树结点P//用作中间值防止树被破坏if(BT不为空){if(BT的左、右孩子都不为空)定义树结点P，将p的左孩子赋值给PBT的左孩子