浙江大学城市学院实验报告
课程名称 数据结构基础 实验项目名称 实验十一 二叉树的进一步操作 学生姓名 专业班级 学号
实验成绩 指导老师（签名 ） 日期 2014-12-25
一. 实验目的和要求
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服务器上自己的文件夹下。
三. 函数的功能说明及算法思路
（包括每个函数的功能说明，及一些重要函数的算法实现思路） 结构定义： 二叉树：
struct BTreeNode{ ElemType data; BTreeNode *lchild; BTreeNode *rchild; };
顺序栈：
struct Stack{
BTreeNode **stack; //存栈元素 int top;
int MaxSize; };
Operations: 二叉树：
void InitBTree( BTreeNode *&BT )//初始化二叉树BT void CreateBTree( BTreeNode *&BT, char *a )
//根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构 void PrintBTree( BTreeNode *BT )//输出二叉树BT void ClearBTree(BTreeNode *&BT)//清除二叉树BT
void InOrder2( BTreeNode *BT )//非递归中序遍历二叉树BT void ChangeBTree(BTreeNode *&BT)
//将二叉树中的所有结点的左右子树进行交换
int CountBTree(BTreeNode *BT)//统计二叉树中的所有结点数并返回 BTreeNode *CopyBTree(BTreeNode *BT)
//复制一棵二叉树，并返回复制得到的二叉树根结点指针 int SimilarTrees(BTreeNode *BT1,BTreeNode *BT2)
//判断两棵二叉树是否相似。所谓相似是指如果两棵二叉树具有相同的树型，则称它们是相似的，否则不是。
BTreeNode * RemoveLeaves(BTreeNode *BT1)
//摘树叶：摘除一棵二叉树上的所有叶子结点后返回一棵新的二叉树。
顺序栈： void InitStack(Stack &S)//初始化栈为空，把栈设置为空并完成栈空间的动态存储分配
void Push(Stack &S,BTreeNode *item)//元素item进栈，即插入到栈顶 BTreeNode *Pop(Stack& S)//删除栈顶元素并返回
bool EmptyStack(Stack& S)//判断S是否为空，若为空则返回true，否则返回false
void ClearStack(Stack& S)//清除栈S中的所有元素，释放动态存储空间
end GeneralTree
算法:
void InOrder2( BTreeNode *BT )//非递归中序遍历二叉树BT {
定义堆栈s 定义树结点P 初始化栈s
while(p不为空或者s不为空) {
if(p不为空)
将p进栈 ；P的值重新赋为p的左孩子 if(s不为空)
将出栈的值赋给p；输出p的根的值 ；P等于p的右边孩子； } }
void ChangeBTree(BTreeNode *&BT)
{//将二叉树中的所有结点的左右子树进行交换 定义树结点P//用作中间值防止树被破坏 if(BT不为空){
if(BT的左、右孩子都不为空)
定义树结点P ，将p的左孩子赋值给 P BT的左孩子等于BT的右孩子 BT的右孩子等于p
递归调用交换左子树；递归调用交换右子树；} }
int CountBTree(BTreeNode *BT)//统计二叉树中的所有结点数并返回 {
if(树为空) 返回0；
else if(BT的左、右孩子等于空) 返回1； else
return 递归调用左孩子个数+递归调用右孩子个数+1； }
BTreeNode *CopyBTree(BTreeNode *BT)
{//复制一棵二叉树，并返回复制得到的二叉树根结点指针 定义树结点P
if(BT为空) 返回空 else {
定义树结点P，并给以内存为
将BT的根结点，左结点，右结点复制给p 返回p；} }