2022年二叉树的基本操作.pdf

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

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

2、实验结果与分析精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 10 页 - - - - - - - - - - 五. 心得体会通过这次实验，我掌握了二叉树的基本操作，对非线性储存结构有了一定的了解，相对于之前的线性储存结构来说，非线性储存结构确实是比较抽象、困难的，在接下来的时间里，要好好对非线性储存结构了解一番。【附录 -源程序】struct BtreeNode elemtype data; /结点值域 BtreeNode *lchild; /定义左孩子指针BtreeNode *rchild

3、; /定义右孩子指针;struct lnode /定义队列结点结构用于二叉树层遍历BtreeNode *data1;lnode *next;struct Queue /定义队列首尾指针精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 10 页 - - - - - - - - - - lnode *front;lnode *back;void initQueue(Queue &Q) /初始化队列=NULL;void insertQueue(Queue &Q,BtreeNode *item) /元素

4、入队列lnode *newptr=new lnode;newptr-data1=item;newptr-next=NULL;if=NULL)=newptr;else=next=newptr;BtreeNode *deleteQueue(Queue &Q) /队首元素出队列BtreeNode *temp=data1;lnode *p=;=p-next;if=NULL)=NULL;delete p;return temp;精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 10 页 - - - - -

5、 - - - - - bool emptyQueue(Queue Q) /判断队列是否为空return =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); /左子叶递归insertBtree(BT-rchild); /右子叶递归bo

6、ol emptyBtree(BtreeNode *BT) /判断二叉树是否为空return BT=NULL;int depthBtree(BtreeNode *BT) /求二叉树的深度精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 10 页 - - - - - - - - - - if(emptyBtree(BT) return 0;elseint dep1=depthBtree(BT-lchild); /左子叶递归int dep2=depthBtree(BT-rchild); /右子叶递归r

7、eturn dep1dep2dep1+1:dep2+1; /判断哪个子叶的深度最大 /树的深度为左右子叶的最大深度加上1void 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) /后序遍历

8、精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 10 页 - - - - - - - - - - if(!emptyBtree(BT)laterorder(BT-lchild); /左子叶递归laterorder(BT-rchild); /右子叶递归coutdatadata=x) /找到，返回truereturn true;elseif(findBtree(BT-lchild,x) /左子叶递归查找return true;if(findBtree(BT-rchild,x) /右子叶递归查找re

9、turn true;return false;void levelorder(BtreeNode *BT) /按层遍历二叉树Queue queue; /用于存放二叉树结点的队列initQueue(queue);精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 10 页 - - - - - - - - - - BtreeNode *P;if(!emptyBtree(BT) /二叉树不为空，根节点入队insertQueue(queue,BT);while(!emptyQueue(queue) /当队

10、列不为空时，队首元素出队列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) /找到，返回其深度return depthBtree(BT);elsem=Get_Su

11、b_Depth(BT-lchild,x); /左右子叶递归，返回深度n=Get_Sub_Depth(BT-rchild,x);return mnm:n;elsereturn 0;精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 10 页 - - - - - - - - - - void printBtree(BtreeNode *BT,int n) /打印二叉树 int i;if(emptyBtree(BT) /二叉树为空，返回return;printBtree(BT-rchild,n+1);

12、/先递归输出右子树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);cout);精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下

13、载 名师归纳 - - - - - - - - - -第 8 页，共 10 页 - - - - - - - - - - #include#include#includetypedef char elemtype;#includevoid main()BtreeNode *Btree;initBtree(Btree);elemtype a,b;cout 请严格按照先序顺序输入二叉树中的数据，以“$”为每个结点的结束标志endl;insertBtree(Btree);cout 二叉树的深度为：depthBtree(Btree)endl;cout 先序遍历二叉树：;preorder(Btree);co

14、utendl;cout 中序遍历二叉树：;midorder(Btree);coutendl;cout 后序遍历二叉树：;laterorder(Btree);coutendl;精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 10 页 - - - - - - - - - - cout 层序遍历二叉树：;levelorder(Btree);coutendl;couta;if(findBtree(Btree,a)cout 查找字符 a 成功！ endl;elsecout 查找失败，没有该字符！endl

15、;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);精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 10 页 - - - - - - - - - -