二叉树的基本操作

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( BTree

3、Node *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_tre

4、e.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; /结点值域 B

5、treeNode *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=ite

6、m;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 ini

7、tBtree(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 depthBtr

8、ee(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); /右子叶递归voi

9、d 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;i

10、f(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);ret

12、urn 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(!empty

13、Btree(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.front

14、=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; /判断哪个子叶的深度最大 /树的深度为左右子叶的最大深度加上1void

16、 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-rch

17、ild); /右子叶递归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(qu

18、eue,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; /结点的值coutlchild,n+1); /再递归输出右子树void PrintBtree(BtreeNode *BT) /二叉树的广义表打印if(!emptyBtree(BT)coutdata;if(!emptyBtree(BT-lchild)|!emptyBtree(BT-rchild)coutlchild);if(!emptyBtree(BT-rchild)coutrchild)