二叉树地基本操作.doc

《二叉树地基本操作.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、eeNode*lchild,*rchild;//定义左右孩子指针};基本操作如下：①voidInitBTree(BTreeNode*&BT);//初始化二叉树BT②voidCreateBTree(BTreeNode*&BT,char*a);//根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构③intEmptyBTree(BTreeNode*BT);//检查二叉树BT是否为空，空返回1，否则返回0④intDepthBTree(BTreeNode*BT);//求二叉树BT的深度并返回该值⑤intFindBTree(BTreeNode*BT,ElemTypex

3、);//查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0⑥voidPreOrder(BTreeNode*BT);//先序遍历二叉树BT⑦voidInOrder(BTreeNode*BT);//中序遍历二叉树BT⑧voidPostOrder(BTreeNode*BT);//后序遍历二叉树BT⑨voidPrintBTree(BTreeNode*BT);//输出二叉树BT⑩voidClearBTree(BTreeNode*&BT);//清除二叉树BT2、选做：实现以下说明的操作函数，要求把函数添加到头文件binary_tree.h中，并在主函数文件test4_

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

5、;//定义左孩子指针BtreeNode*rchild;//定义右孩子指针};structlnode{//定义队列结点结构用于二叉树层遍历BtreeNode*data1;lnode*next;};structQueue{//定义队列首尾指针lnode*front;lnode*back;};voidinitQueue(Queue&Q)//初始化队列{Q.front=Q.back=NULL;}voidinsertQueue(Queue&Q,BtreeNode*item)//元素入队列{lnode*newptr=newlnode;newptr->data1=item;ne

6、wptr->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;deletep;returntemp;}boolemptyQueue(QueueQ)//判断队列是否为空{returnQ.front==

7、NULL;}voidinitBtree(BtreeNode*&BT)//二叉树的初始化{BT=NULL;}voidinsertBtree(BtreeNode*&BT)//创建二叉树{elemtypech;ch=getchar();if(ch=='$')//判断是不是结束标志BT=NULL;else{BT=newBtreeNode;//创建结点BT->data=ch;//赋值insertBtree(BT->lchild);//左子叶递归insertBtree(BT->rchild);//右子叶递归}}boolemptyBtree(BtreeNode*BT)//判断二

8、叉树是否为