数据结构基础实验10

浙江大学城市学院实验报告 课程名称 数据结构基础 实验项目名称 实验十 二叉树的基本操作 学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期 1. 实验目的和 1、掌握二叉树的链式存储结构。 2、掌握在二叉链上的二叉树操作的实现原理与。 3、进一步掌握递归算法的设计方法。 2. 实验内容 1、建立头文件test10.h，定义二叉树的链式存储结构，并编写二叉树的各种基本操作实现函数。同时建立一个验证操作实现的主函数文件test10.cpp，编译并调试程序，直到正确运行。 说明：二叉树的基本操作可包括： (1) void InitBTree( BTreeNode *&BT ) //初始化二叉树BT (2) void CreateBTree( BTreeNode *&BT, char *a ) //根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构 (3) int EmptyBTree( BTreeNode *BT) //检查二叉树BT是否为空，空返回1，否则返回0 (4) int DepthBTree( BTreeNode *BT) //求二叉树BT的深度并返回该值 (5) int FindBTree( BTreeNode *BT, ElemType x) //查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 (6) void PreOrder( BTreeNode *BT) //先序遍历二叉树BT (7) void InOrder( BTreeNode *BT) //中序遍历二叉树BT (8) void PostOrder( BTreeNode *BT) //后序遍历二叉树BT (9) void LevelOrder( BTreeNode *BT ) //按层次遍历二叉树BT (10) void PrintBTree( BTreeNode *BT ) //输出二叉树BT (11) void ClearBTree( BTreeNode *&BT ) //清除二叉树BT 2、以下内容为第二次实验完成： (1) 请编写函数实现中序遍历的非递归算法。将此函数输入到前述头文件test10.h中，并在主函数文件test10.cpp中增加测试语句测试这个函数的正确性。注意需要用到栈的有关操作，可使用已编制过的栈的基本操作文件test9_stack.h来实现。 提示： 二叉树中序遍历的非递归算法就是运用栈这种数据结构将递归的中序遍历转换成非递归的中序遍历，采用的是间接转换方式。中序遍历非递归算法的N-S流程图如下： 注意：栈中存放的应该是指向结点的指针，即结点的地址，而不是结点的值。因为，只有根据结点的地址才能在二叉树中查找到该结点。 (2) 完成以下算法的设计，并将这些函数输入到前述头文件test10.h中，在主函数文件test10.cpp中增加测试语句测试其正确性。 (a) 将二叉树中的所有结点的左右子树进行交换，函数原型如下： Int ChangeBTree(BTreeNode *BT); (b) 统计二叉树中的所有结点数，函数原型如下： Int CountBTree(BTreeNode *BT); (c) 复制一棵二叉树，并返回复制得到的二叉树根结点指针，函数原型如下： BTreeNode * CopyBTree(BTreeNode *BT); 3、填写实验报告，实验报告文件取名为report10.doc。 4、上传实验报告文件report10.doc 、源程序文件test10.cpp及test10.h到Ftp服务器上（ ftp://10.61.14.240:5000 ）自己的文件夹下。 三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路） void InitBTree(BTreeNode *&BT ) //初始化二叉树BT { BT=NULL; } void CreateBTree( BTreeNode *&BT, char *a ) //根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构 { const int MaxSize=10; BTreeNode*s[MaxSize]; int top=-1; BT=NULL; BTreeNode*p; int k; int i=0; while(a[i]){ switch(a[i]){ case' ':break; case'(': if(top==MaxSize-1){ cout<<"栈空间太小，请增加MaxSize的值！"<data=a[i];p->left=p->right=NULL; if(BT==NULL) BT=p; else{ if(k==1) s[top]->left=p; else s[top]->right=p; } } i++; } } int EmptyBTree( BTreeNode *BT)//检查二叉树BT是否为空，空返回1，否则返回0 { return BT==NULL; } int DepthBTree( BTreeNode *BT) //求二叉树BT的深度并返回该值 { if(BT==NULL) return 0; else{ int dep1=DepthBTree(BT->left); int dep2=DepthBTree(BT->right); if(dep1>dep2) return dep1+1; else return dep2+1; } int FindBTree( BTreeNode *BT, ElemType x) //查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 { if(BT==NULL) return false; else{ if(BT->data==x){ x=BT->data; return true; } else{ if(FindBTree(BT->left,x)) return true; if(FindBTree(BT->right,x)) return true; return false; } } } void PreOrder(BTreeNode* BT) //先序遍历二叉树BT { if(BT!=NULL){ cout<data<<' '; PreOrder(BT->left); PreOrder(BT->right); } } void InOrder(BTreeNode* BT) //中序遍历二叉树BT { if(BT!=NULL){ InOrder(BT->left); cout<data<<' '; InOrder(BT->right); } } void PostOrder(BTreeNode* BT) //后序遍历二叉树BT { if(BT!=NULL){ PostOrder(BT->left); PostOrder(BT->right); cout<data<<' '; } } void LevelOrder(BTreeNode* BT) //按层次遍历二叉树BT { const int MaxSize=30; BTreeNode* q[MaxSize]; int front=0,rear=0; BTreeNode* p; if(BT!=NULL){ rear=(rear+1)%MaxSize; q[rear]=BT; } while(front!=rear){ front=(front+1)%MaxSize; p=q[front]; cout<data<<' '; if(p->left!=NULL){ rear=(rear+1)%MaxSize; q[rear]=p->left; } if(p->right!=NULL){ rear=(rear+1)%MaxSize; q[rear]=p->right; } } } void PrintBTree(BTreeNode*BT) //输出二叉树BT { if(BT!=NULL){ cout<data; if(BT->left!=NULL || BT->right!=NULL){ cout<<'('; PrintBTree(BT->left); if(BT->right!=NULL) cout<<','; PrintBTree(BT->right); cout<<'('; } } } void ClearBTree(BTreeNode*&BT) //清除二叉树BT { if(BT!=NULL){ ClearBTree(BT->left); ClearBTree(BT->right); delete BT; BT=NULL; } } 四. 实验结果与

分析

定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析

（包括运行结果截图、结果分析等） 五. 心得体会 （记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。） 【附录----源程序】 Test10.h void InitBTree( BTreeNode *&BT ) //初始化二叉树BT { BT=NULL; } void CreateBTree( BTreeNode *&BT, char *a ) {//根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构 const int MaxSize=10; BTreeNode*s[MaxSize]; int top=-1; BT=NULL; BTreeNode*p; int k; int i=0; while(a[i]){ switch(a[i]){ case' ': break; case'(': if(top==MaxSize-1){ cout<<"栈空间太小，请增加MaxSize的值！"<data=a[i]; p->left=p->right=NULL; if(BT==NULL) BT=p; else{ if(k==1) s[top]->left=p; else s[top]->right=p; } } i++; } } int EmptyBTree( BTreeNode *BT) {//检查二叉树BT是否为空，空返回1，否则返回0 return BT==NULL; } int DepthBTree( BTreeNode *BT) //求二叉树BT的深度并返回该值 { if(BT==NULL) return 0; else{ int dep1=DepthBTree(BT->left); int dep2=DepthBTree(BT->right); if(dep1>dep2) return dep1+1; else return dep2+1; } } int FindBTree( BTreeNode *BT, ElemType x) {//查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 if(BT==NULL) return false; else{ if(BT->data==x){ x=BT->data; return true; } else{ if(FindBTree(BT->left,x)) return true; if(FindBTree(BT->right,x)) return true; return false; } } } void PreOrder( BTreeNode *BT) //先序遍历二叉树BT { if(BT!=NULL){ cout<data<<' '; PreOrder(BT->left); PreOrder(BT->right); } } void InOrder( BTreeNode *BT) //中序遍历二叉树BT { if(BT!=NULL){ InOrder(BT->left); cout<data<<' '; InOrder(BT->right); } } void PostOrder( BTreeNode *BT) //后序遍历二叉树BT { if(BT!=NULL){ PostOrder(BT->left); PostOrder(BT->right); cout<data<<' '; } } void LevelOrder( BTreeNode *BT ) //按层次遍历二叉树BT { const int MaxSize=30; BTreeNode* q[MaxSize]; int front=0,rear=0; BTreeNode* p; if(BT!=NULL){ rear=(rear+1)%MaxSize; q[rear]=BT; } while(front!=rear){ front=(front+1)%MaxSize; p=q[front]; cout<data<<' '; if(p->left!=NULL){ rear=(rear+1)%MaxSize; q[rear]=p->left; } if(p->right!=NULL){ rear=(rear+1)%MaxSize; q[rear]=p->right; } } } void PrintBTree( BTreeNode *BT ) //输出二叉树BT { if(BT!=NULL){ cout<data; if(BT->left!=NULL || BT->right!=NULL){ cout<<','; PrintBTree(BT->right); cout<<')'; } } } void ClearBTree( BTreeNode *&BT ) //清除二叉树BT { if(BT!=NULL){ ClearBTree(BT->left); ClearBTree(BT->right); delete BT; BT=NULL; } } Test10.cpp #include #include typedef char ElemType; struct BTreeNode{ ElemType data; BTreeNode*left; BTreeNode*right; }; #include"test10.h" void main() { BTreeNode* bt; InitBTree( bt ); char b[50]; cout<<"输入二叉树用广义表表示的字符串："<>x; if(FindBTree(bt,x)) cout<<"查找字符"<