浙大城院数据结构report11_浙大城院
浙大城院数据结构report11由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“浙大城院”。
浙江大学城市学院实验报告
课程名称
数据结构基础
实验项目名称
实验十一
二叉树的进一步操作
学生姓名
专业班级
学号
实验成绩
指导老师（签名）
日期
三.函数的功能说明及算法思路
（包括每个函数的功能说明，及一些重要函数的算法实现思路）算法
//非递归中序遍历二叉树BT
void In_Order2(BTreeNode *BT){
定义一个堆栈s，并初始化堆栈
定义一个和BT相等的树结点P
while(堆栈不为空或者p不为空)
{
if(p不为空)
将p进栈 ；P重新赋值等于p的左孩纸
else
P等于出栈的值；输出p的根的值 ；P等于p的右边孩纸；
} }
//将二叉树中的所有结点的左右子树进行交换
void ChangeBTree(BTreeNode *BT){ 定义一个和BT相等的树结点P//用作中间值防止树被破坏
if(BT不是空)
{ 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不为空)
{ 为p开辟内存
依次复制根节点，左节点，右节点；
返回p；}
else
返回空； }
//如果两棵二叉树具有相同的树型，则称它们是相似的 int SimilarTrees(BTreeNode *BT1,BTreeNode *BT2){
设置变量like1以及like2用于保留左子树以及右子树是否相似的值
if(BT1以及BT2等于空)
返回1；
else
if(BT1和BT2中只有一个为空)
返回0；
else
{
like1=递归函数，判断BT1以及BT2的左孩纸是否相等
like2=递归函数，判断BT1以及BT2的右孩纸是否相等
return
like1&&like2;
} }
//摘除一棵二叉树上的所有叶子结点后返回一棵新的二叉树
BTreeNode * RemoveLeaves(BTreeNode *BT1){
if(BT1为空)
return空值;
else
if(BT1左孩纸和右孩纸为空值)
删除BT1，并且返回NULL
else
{ BT1->lchild=递归调用BT1的左孩纸
BT1->rchild=递归调用BT1的右孩纸；
}
返回BT1； } 四.实验结果与分析（包括运行结果截图、结果分析等）
五.心得体会
失败点:在相似的二叉树理解上费时了很久，将二叉树相似和二叉树相等不能很好的区分
【附录----源程序】
test4_2.cpp #include #include #include
typedef char ElemType;
struct BTreeNode {
ElemType data;
BTreeNode *lchild;
BTreeNode *rchild;};
#include“binary_tree.h”
void main(){
BTreeNode *T1,*T2,*T3;
char ch[80],x;//x用于存放查找的数据
InitBTree(T1);
//初始化二叉树
cout
EmptyBTree(T1)?cout
printf(“请输入广义表:”);gets(ch);
//将广义表保存在ch字符串中
CreateBTree(T1,ch);
//建立二叉树
EmptyBTree(T1)?cout
cout
printf(“输入要查找的元素1:”);cin>>x;
FindBTree(T1,x)?cout
printf(“输入要查找的元素2:”);cin>>x;
FindBTree(T1,x)?cout
cout
PreOrder(T1);cout
cout
InOrder(T1);cout
cout
PostOrder(T1);cout
cout
LevelOrder(T1);cout
cout
PrintBTree(T1);cout
/*————————————————————————————————*/
cout
cout
In_Order2(T1);cout
printf(“交换前:”);PrintBTree(T1);cout
ChangeBTree(T1);
//交换左右子树
printf(“交换后:”);PrintBTree(T1);cout
cout
InitBTree(T2);
//初始化二叉树
T2=CopyBTree(T1);
cout
//输出二叉树
PrintBTree(T1);cout
cout
//输出二叉树
PrintBTree(T2);cout
printf(“请输入广义表:”);
gets(ch);
//将广义表保存在ch字符串中
CreateBTree(T3,ch);
//建立二叉树
if(SimilarTrees(T1,T3))
//比较T1与T3是否相似
cout
cout
if(SimilarTrees(T1,T2))
//比较T1与T2是否相似
cout
cout
cout
//输出二叉树
PrintBTree(T1);cout
RemoveLeaves(T1);
//摘除叶子结点
cout
//输出二叉树
PrintBTree(T1);cout
binary_tree.h
/*——————————————顺序栈的操作——————————————*/
struct Stack { BTreeNode **stack;// 存栈元素
int top;
// 栈顶指示器
};
void InitStack(Stack &S)
//构造一个空栈 S {
}
int EmptyStack(Stack S)
//若栈S为空栈返回1，否则返回0 {
}
void Push(Stack &S, BTreeNode * item)
//元素 item进栈
{
}
BTreeNode * Pop(Stack &S)
//栈S的栈顶元素出栈并返回
{
BTreeNode * temp;
if(S.top==-1)
{ cout
if(S.top==S.MaxSize-1)
{
} S.top++;
S.stack[S.top]=item;S.stack=(BTreeNode**)realloc(S.stack,S.MaxSize*sizeof(BTreeNode *)*2);
S.MaxSize*=2;
return S.top==-1;S.MaxSize=10;
S.stack=(BTreeNode**)malloc(S.MaxSize *sizeof(BTreeNode *));
if(!S.stack){
}
S.top=-1;
cout
exit(1);
int MaxSize;
// 栈的最大长度
}
} exit(1);
S.top--;
temp=S.stack[S.top+1];
return temp;
BTreeNode * Peek(Stack S)
//取栈S的当前栈顶元素并返回
{
}
/*——————————————循环队列的操作———————————*/ struct Queue {
};
void InitQueue(Queue &Q)//初始化循环队列Q {
}
int EmptyQueue(Queue Q)//判断队列是否为空,空返回1,否则返回0 {
}
void EnQueue(Queue &Q , BTreeNode * item)//进队列
{
if((Q.rear+1)%Q.MaxSize==Q.front)//空间不足，扩大2倍
{
} int k=sizeof(BTreeNode *);
Q.queue=(BTreeNode **)realloc(Q.queue,2*Q.MaxSize*k);
if(Q.rear!=Q.MaxSize-1)
{
//移动队列内容，必须要做
}
Q.MaxSize=2*Q.MaxSize;
//修改队列最大空间
for(int i=0;i
Q.queue[i+Q.MaxSize]=Q.queue[i];
Q.rear=Q.rear+Q.MaxSize;
return Q.rear==Q.front;Q.MaxSize=20;
Q.queue =(BTreeNode **)malloc(Q.MaxSize*sizeof(BTreeNode *));
Q.rear=Q.front =0;BTreeNode **queue;
int MaxSize;
//队列最大存储数
int front;
//头指针，若队列不空，指向队列头元素的前一个位置
int rear;
//尾指针，若队列不空，指向队列尾元素
return S.stack[S.top];
}
Q.rear=(Q.rear+1)%Q.MaxSize;
//元素入队
Q.queue[Q.rear]=item;
BTreeNode * OutQueue(Queue &Q){
if(Q.rear==Q.front)
{
} printf(“队列已空无数据元素出队列!n”);
exit(1);
//先修改front位置，后取走元素
}
/*—————————————---—树的操作————————————*/ //初始化二叉树BT
void InitBTree(BTreeNode *&BT){
} //根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构
void CreateBTree(BTreeNode *&BT, char *a){
Stack s;//堆栈
BTreeNode *p, *t;
//p指向新申请的结点，t指向栈顶结点
int k, i=0;
//k=1表示将处理左子树，k=2表示处理右子树
BT=NULL;
InitStack(s);//初始化堆栈
while(a[i])//一个个读入字符进行处理直到读到' '为止
{
switch(a[i])
{
case ' ':
break;
case '(':
Push(s, p);k=1;break;
BT=NULL;Q.front =(Q.front +1)% Q.MaxSize;
return Q.queue[Q.front];
case ')':
Pop(s);break;
case ',':
k=2;break;
default:
//只可能是字符，即结点值
p =(BTreeNode *)malloc(sizeof(BTreeNode));
p->data = a[i];
p->lchild = p->rchild = NULL;
if(BT== NULL)
BT = p;
else
}
}
}
{
}
t = Peek(s);if(k==1)
t->lchild = p;
else
t->rchild = p;
i++;
//检查二叉树BT是否为空，空返回1，否则返回0
int EmptyBTree(BTreeNode *BT){
} //求二叉树BT的深度并返回该值
int DepthBTree(BTreeNode *BT)
{
} //查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 int FindBTree(BTreeNode *BT, ElemType x){
if(BT==NULL)
return 0;if(BT==NULL)
//空树深度为0
return 0;
return BT==NULL;
else
{
} int dep1=DepthBTree(BT->lchild);
//先求根结点左子树的深度
int dep2=DepthBTree(BT->rchild);//再求根结点右子树的深度
if(dep1>dep2)
//返回最大值，并加上根结点这一层
else return dep2+1;
return dep1+1;
else
{
if(BT->data==x)return 1;
else
{
if(FindBTree(BT->lchild,x))return 1;
if(FindBTree(BT->rchild,x))return 1;
}
} } return 0;
//先序遍历二叉树BT
void PreOrder(BTreeNode *BT)
{
}
//中序遍历二叉树BT
void InOrder(BTreeNode *BT)
{
if(BT)
{ if(BT){
} coutdata
PreOrder(BT->lchild);
//先序遍历左子树
PreOrder(BT->rchild);
//先序遍历右子树
InOrder(BT->lchild);
//中序遍历左子树
}
//后序遍历二叉树BT
void PostOrder(BTreeNode *BT)
{
}
//输出二叉树BT
void PrintBTree(BTreeNode *BT)
{
if(BT)
//树非空
{
coutdata;//输出根结点
if(BT->lchild!= NULL || BT->rchild!= NULL)//若非叶子结点，则递归调用输出左右子树
{ if(BT){
} PostOrder(BT->lchild);
//后序遍历左子树
PostOrder(BT->rchild);
//后序遍历右子树
coutdata
//访问根结点
}
coutdata
InOrder(BT->rchild);
//中序遍历右子树
}
}
} cout
PrintBTree(BT->lchild);
if(BT->rchild!= NULL)
{
}
cout
cout
PrintBTree(BT->rchild);
//清除二叉树BT void ClearBTree(BTreeNode *&BT)
{
if(BT){
ClearBTree(BT->lchild);//先递归删除左子树
ClearBTree(BT->rchild);//再递归删除右子树
free(BT);//最后释放根结点
BT=NULL;//根指针为空
}
/*——————————————附加的操作—————————————————*/ //按层次遍历二叉树BT
void LevelOrder(BTreeNode *BT)
//按层次遍历: 利用队列, 每次访问队头结点，一旦访问某结点,它的左右孩子入队列，该结点出队列
{
Queue q;// 定义一个队列
InitQueue(q);// 初始化队列
if(BT)// 树不空
{
} EnQueue(q,BT);// 根结点入队
while(!EmptyQueue(q))// 队列不空 {
} BT = OutQueue(q);// 出队
coutdata
if(BT->lchild!= NULL)
EnQueue(q, BT->lchild);
}
if(BT->rchild!= NULL)
EnQueue(q, BT->rchild);
}
int Get_Sub_Depth(BTreeNode *BT , ElemType x){
} int m,n;if(BT){
} else{
} return 0;if(BT->data==x)
else {
} m=Get_Sub_Depth(BT->lchild,x);n=Get_Sub_Depth(BT->rchild,x);return m>n?m:n;return DepthBTree(BT);/*--------------------实验11要求的操作-*/ //非递归中序遍历二叉树BT
void In_Order2(BTreeNode *BT){
}
//将二叉树中的所有结点的左右子树进行交换
void ChangeBTree(BTreeNode *BT){ Stack s;
BTreeNode *p=BT;
InitStack(s);
// 初始化堆栈
while(p!=NULL ||!EmptyStack(s))
{
} if(p)
{
}
else
{
} p=Pop(s);
coutdata
p=p->rchild;
Push(s, p);
p=p->lchild;
} BTreeNode *p;
if(BT)
{
} p=BT->lchild;
BT->lchild=BT->rchild;
BT->rchild=p;
ChangeBTree(BT->lchild);//递归交换左子树
ChangeBTree(BT->rchild);//递归交换右子树
//统计二叉树中的所有结点数
int CountBTree(BTreeNode *BT){
}
//复制一棵二叉树，并返回复制得到的二叉树根结点指针
BTreeNode *CopyBTree(BTreeNode *BT){
BTreeNode *p;
if(BT)
{ if(!BT)return 0;else
if(BT->lchild==NULL&&BT->rchild==NULL)
else return CountBTree(BT->lchild)+CountBTree(BT->rchild)+1;return 1;
p=(BTreeNode *)malloc(sizeof(BTreeNode));
}
//如果两棵二叉树具有相同的树型，则称它们是相似的 int SimilarTrees(BTreeNode *BT1,BTreeNode *BT2){
int like1,like2;
if(BT1==NULL && BT2==NULL)
return 1;
}
else return NULL;p->data=BT->data;
p->lchild=CopyBTree(BT->lchild);
p->rchild=CopyBTree(BT->rchild);
return p;
}
else
if(BT1==NULL || BT2==NULL)
return 0;
else
{
} like1=SimilarTrees(BT1->lchild,BT2->lchild);//判断左子树是否相似
like2=SimilarTrees(BT1->rchild,BT2->rchild);//判断右子树是否相似
return
like1&&like2;
//摘除一棵二叉树上的所有叶子结点后返回一棵新的二叉树
BTreeNode * RemoveLeaves(BTreeNode *BT1){
} if(BT1==NULL)
return NULL;else
if(BT1->lchild==NULL&&BT1->rchild==NULL)
{
}
else
{
} BT1->lchild=RemoveLeaves(BT1->lchild);//检查左子树
BT1->rchild=RemoveLeaves(BT1->rchild);//检查右子树
free(BT1);
return NULL;
return BT1;
