二叉树的基本操作(11页).doc

《二叉树的基本操作(11页).doc》由会员分享，可在线阅读，更多相关《二叉树的基本操作(11页).doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验十 二叉树的基本操作 学生姓名 吴奇 专业班级 信管1204 学号 31201403 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1、掌握二叉树的链式存储结构。2、掌握在二叉链表上的二叉树操作的实现原理与方法。3、进一步掌握递归算法的设计方法。二. 实验内容1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test4_1.cpp，验证头文件中各个操作。二叉树二叉链表存储表示如下：struct BTreeNode ElemType data

2、; / 结点值域 BTreeNode *lchild , *rchild ; / 定义左右孩子指针 ;基本操作如下：void InitBTree( BTreeNode *&BT ); /初始化二叉树BT void CreateBTree( BTreeNode *&BT, char *a ); /根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构 int EmptyBTree( BTreeNode *BT); /检查二叉树BT是否为空，空返回1，否则返回0 int DepthBTree( BTreeNode *BT);/求二叉树BT的深度并返回该值 int FindBTree( BTre

3、eNode *BT, ElemType x); /查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 void PreOrder( BTreeNode *BT);/先序遍历二叉树BTvoid InOrder( BTreeNode *BT);/中序遍历二叉树BTvoid PostOrder( BTreeNode *BT); /后序遍历二叉树BT void PrintBTree( BTreeNode *BT ); /输出二叉树BT void ClearBTree( BTreeNode *&BT ); /清除二叉树BT2、选做：实现以下说明的操作函数，要求把函数添加到头文件binary_tr

4、ee.h中，并在主函数文件test4_1.cpp中添加相应语句进行测试。void LevelOrder( BTreeNode *BT )/二叉树的层序遍历int Get_Sub_Depth( BTreeNode *T , ElemType x)/求二叉树中以元素值为x的结点为根的子树的深度3、填写实验报告，实验报告文件取名为report10.doc。4、上传实验报告文件report10.doc 、源程序文件test4_1.cpp及binary_tree.h到Ftp服务器上自己的文件夹下。三. 函数的功能说明及算法思路 struct BtreeNode elemtype data; /结点值域

5、BtreeNode *lchild; /定义左孩子指针BtreeNode *rchild; /定义右孩子指针;struct lnode /定义队列结点结构用于二叉树层遍历BtreeNode *data1;lnode *next;struct Queue /定义队列首尾指针lnode *front;lnode *back;void initQueue(Queue &Q) /初始化队列Q.front=Q.back=NULL;void insertQueue(Queue &Q,BtreeNode *item) /元素入队列lnode *newptr=new lnode;newptr-data1=it

6、em;newptr-next=NULL;if(Q.back=NULL)Q.front=Q.back=newptr;elseQ.back=Q.back-next=newptr;BtreeNode *deleteQueue(Queue &Q) /队首元素出队列BtreeNode *temp=Q.front-data1;lnode *p=Q.front;Q.front=p-next;if(Q.front=NULL)Q.back=NULL;delete p;return temp;bool emptyQueue(Queue Q) /判断队列是否为空return Q.front=NULL;void in

7、itBtree(BtreeNode *&BT) /二叉树的初始化BT=NULL;void insertBtree(BtreeNode *&BT) /创建二叉树elemtype ch;ch=getchar();if(ch=$) /判断是不是结束标志BT=NULL;elseBT=new BtreeNode; /创建结点BT-data=ch; /赋值insertBtree(BT-lchild); /左子叶递归insertBtree(BT-rchild); /右子叶递归bool emptyBtree(BtreeNode *BT) /判断二叉树是否为空return BT=NULL;int depthBt

8、ree(BtreeNode *BT) /求二叉树的深度if(emptyBtree(BT) return 0;elseint dep1=depthBtree(BT-lchild); /左子叶递归int dep2=depthBtree(BT-rchild); /右子叶递归return dep1dep2?dep1+1:dep2+1; /判断哪个子叶的深度最大 /树的深度为左右子叶的最大深度加上1void preorder(BtreeNode *BT) /前序遍历if(!emptyBtree(BT)coutdatalchild); /左子叶递归preorder(BT-rchild); /右子叶递归vo

9、id midorder(BtreeNode *BT) /中序遍历if(!emptyBtree(BT)midorder(BT-lchild); /左子叶递归coutdatarchild); /右子叶递归void laterorder(BtreeNode *BT) /后序遍历if(!emptyBtree(BT)laterorder(BT-lchild); /左子叶递归laterorder(BT-rchild); /右子叶递归coutdatadata=x) /找到，返回truereturn true;elseif(findBtree(BT-lchild,x) /左子叶递归查找return true;

10、if(findBtree(BT-rchild,x) /右子叶递归查找return true;return false;void levelorder(BtreeNode *BT) /按层遍历二叉树Queue queue; /用于存放二叉树结点的队列initQueue(queue);BtreeNode *P;if(!emptyBtree(BT) /二叉树不为空，根节点入队insertQueue(queue,BT);while(!emptyQueue(queue) /当队列不为空时，队首元素出队列P=deleteQueue(queue);coutdatalchild!=NULL) /当左右子叶不为

11、空时，递归insertQueue(queue,P-lchild);if(P-rchild!=NULL)insertQueue(queue,P-rchild);int Get_Sub_Depth(BtreeNode *BT,elemtype x)/求二叉树中以元素值为x的结点为根的子树的深度int m,n;if(!emptyBtree(BT) /二叉树非空if(BT-data=x) /找到，返回其深度return depthBtree(BT);elsem=Get_Sub_Depth(BT-lchild,x); /左右子叶递归，返回深度n=Get_Sub_Depth(BT-rchild,x);re

12、turn mn?m:n;elsereturn 0;void printBtree(BtreeNode *BT,int n) /打印二叉树 int i;if(emptyBtree(BT) /二叉树为空，返回return;printBtree(BT-rchild,n+1); /先递归输出右子树for(i=0;in;i+) cout ; /前导空格，表示层次cout-;coutdata; /结点的值coutlchild,n+1); /再递归输出右子树void PrintBtree(BtreeNode *BT) /二叉树的广义表打印if(!emptyBtree(BT)coutdata;if(!empt

13、yBtree(BT-lchild)|!emptyBtree(BT-rchild)coutlchild);if(!emptyBtree(BT-rchild)coutrchild);coutdata1=item;newptr-next=NULL;if(Q.back=NULL)Q.front=Q.back=newptr;elseQ.back=Q.back-next=newptr;BtreeNode *deleteQueue(Queue &Q) /队首元素出队列BtreeNode *temp=Q.front-data1;lnode *p=Q.front;Q.front=p-next;if(Q.fron

14、t=NULL)Q.back=NULL;delete p;return temp;bool emptyQueue(Queue Q) /判断队列是否为空return Q.front=NULL;void initBtree(BtreeNode *&BT) /二叉树的初始化BT=NULL;void insertBtree(BtreeNode *&BT) /创建二叉树elemtype ch;ch=getchar();if(ch=$) /判断是不是结束标志BT=NULL;elseBT=new BtreeNode; /创建结点BT-data=ch; /赋值insertBtree(BT-lchild); /左

15、子叶递归insertBtree(BT-rchild); /右子叶递归bool emptyBtree(BtreeNode *BT) /判断二叉树是否为空return BT=NULL;int depthBtree(BtreeNode *BT) /求二叉树的深度if(emptyBtree(BT) return 0;elseint dep1=depthBtree(BT-lchild); /左子叶递归int dep2=depthBtree(BT-rchild); /右子叶递归return dep1dep2?dep1+1:dep2+1; /判断哪个子叶的深度最大 /树的深度为左右子叶的最大深度加上1voi

16、d preorder(BtreeNode *BT) /前序遍历if(!emptyBtree(BT)coutdatalchild); /左子叶递归preorder(BT-rchild); /右子叶递归void midorder(BtreeNode *BT) /中序遍历if(!emptyBtree(BT)midorder(BT-lchild); /左子叶递归coutdatarchild); /右子叶递归void laterorder(BtreeNode *BT) /后序遍历if(!emptyBtree(BT)laterorder(BT-lchild); /左子叶递归laterorder(BT-rc

17、hild); /右子叶递归coutdatadata=x) /找到，返回truereturn true;elseif(findBtree(BT-lchild,x) /左子叶递归查找return true;if(findBtree(BT-rchild,x) /右子叶递归查找return true;return false;void levelorder(BtreeNode *BT) /按层遍历二叉树Queue queue; /用于存放二叉树结点的队列initQueue(queue);BtreeNode *P;if(!emptyBtree(BT) /二叉树不为空，根节点入队insertQueue(q

18、ueue,BT);while(!emptyQueue(queue) /当队列不为空时，队首元素出队列P=deleteQueue(queue);coutdatalchild!=NULL) /当左右子叶不为空时，递归insertQueue(queue,P-lchild);if(P-rchild!=NULL)insertQueue(queue,P-rchild);int Get_Sub_Depth(BtreeNode *BT,elemtype x)/求二叉树中以元素值为x的结点为根的子树的深度int m,n;if(!emptyBtree(BT) /二叉树非空if(BT-data=x) /找到，返回其

19、深度return depthBtree(BT);elsem=Get_Sub_Depth(BT-lchild,x); /左右子叶递归，返回深度n=Get_Sub_Depth(BT-rchild,x);return mn?m:n;elsereturn 0;void printBtree(BtreeNode *BT,int n) /打印二叉树 int i;if(emptyBtree(BT) /二叉树为空，返回return;printBtree(BT-rchild,n+1); /先递归输出右子树for(i=0;in;i+) cout ; /前导空格，表示层次cout-;coutdata; /结点的值c

20、outlchild,n+1); /再递归输出右子树void PrintBtree(BtreeNode *BT) /二叉树的广义表打印if(!emptyBtree(BT)coutdata;if(!emptyBtree(BT-lchild)|!emptyBtree(BT-rchild)coutlchild);if(!emptyBtree(BT-rchild)coutrchild);cout);Btree.cpp#include#include#includetypedef char elemtype;#includeBtree.hvoid main()BtreeNode *Btree;initBt

21、ree(Btree);elemtype a,b;cout请严格按照先序顺序输入二叉树中的数据，以“$”为每个结点的结束标志endl;insertBtree(Btree);cout二叉树的深度为：depthBtree(Btree)endl;cout先序遍历二叉树：;preorder(Btree);coutendl;cout中序遍历二叉树：;midorder(Btree);coutendl;cout后序遍历二叉树：;laterorder(Btree);coutendl;cout层序遍历二叉树：;levelorder(Btree);coutendl;couta;if(findBtree(Btree,a)cout查找字符a成功！endl;elsecout查找失败，没有该字符！endl;coutb;if(Get_Sub_Depth(Btree,b)=0)cout未查询到该结点！endl;elsecout结点元素值为x的深度为：Get_Sub_Depth(Btree,b)endl;cout二叉树的广义表打印如下图：endl;PrintBtree(Btree);coutendl;cout二叉树打印如下图：endl;printBtree(Btree,depthBtree(Btree);-第 11 页-