二叉树实验报告-7

重庆交通大学信息科学与工程学院报告书专业：计算机科学与技术课程名称：数据结构题目：二叉树实验班级：设计者：完成时间：设计要求试实现一棵二叉树,二叉树的结点结构和存储结构由学生自行设计与完成，主要完成以下功能：1、二叉树的建立2、二叉树的各种遍历3、实现插入功能4、实现删除功能5、定位功能6、实现搜索功能7、统计叶结点数量和分支结点的数量8、计算二叉树的高度等实验完成后，将实验报告电子版和源代码提交。另将实验报告打印一份上交到软件中心实验室。实验报告的内容请参见实验报告模板文件。设计思路和主要步骤首先进行数据存储结构和相关类、结构的分析。本实验程序采用链式存储方式，定义类BtreeNode充当数据承载着，类Btree用于实现所有要求的操作，其中Btree类定义为BtreeNode类的友元类，使其可以方便的操作BtreeNode类的私有成员left和right。在Btre类中定义一个BtreNode类型的root指针，用于二叉树的根指针。将其设置为私有成员实现数据封装。设置一组操作函数，均为私有成员。具体函数如下:voidCreateBtree(char*a);//创建二叉树 voidtraverse(BtreeNod*&bt,intmark);//遍历二叉树 boolinsert(BtreeNod*&bt,chara);//插入数据 voiddel(BtreeNod*&bt,chara);//删除数据 intDepth(BtreeNod*&bt);//求深度 intCount(BtreeNod*&bt);//节点数 intleafCount(BtreeNod*&bt);//叶子数 voidprint(BtreeNod*&bt);//广义表形式输出 voidfind(BtreeNod*&bt,chara);//查找 voidClear(BtreeNod*&bt);//删除二叉树创建二叉树。二叉树的创建使用了广义表的形式创建，更具输入的广义表的形式来创建相应的二叉树，当然也可以采用前序法创建二叉树，二叉树已@作为结束标志符号，‘，’表示为空！遍历二叉树。二叉树的遍历共采用3中方式，前序遍历、中序遍历、后序遍历，其基本方法基本相同，均采用递归的方法。至于第四种方法，按层遍历，实质上也差不了多少，在本程序中未实现按层遍历。前序遍历的代码如下:if(mark==1)//根据mark的值确定以何种方式遍历，mark=1是前序遍历 { if(bt!=NULL) { cout<<bt->data<<""; traverse(bt->left,mark);//递归 traverse(bt->right,mark); } }插入功能。插入功能采用根据插入值的大小来决定插入的具体位置，比当前节点的值大，则向右子树方向递归，否则向左子树方向递归。大概代码如下: if(bt==NULL){bt=newBtreeNod;bt->left=NULL;bt->right=NULL;bt->data=a;returntrue;}elseif(bt->data==a){cout<<"插入"<<a<<"失败:元素已存在!"<<endl;returnfalse;}elseif(bt->data>a)returninsert(bt->left,a);elsereturninsert(bt->right,a);删除节点。节点的删除将会删除其下面的子节点。也是采用递归的方法实现。具体代码如下:if(bt==NULL){cout<<"没有要删除的元素!"<<endl;return;}elseif(bt!=NULL&&bt->data==a){BtreeNod*oldNode=bt;if(bt->left==NULL){if(bt->right==NULL){bt=NULL;oldNode=NULL;deletebt;deleteoldNode;}else{oldNode=NULL;bt=bt->right;bt->right=bt->right;deleteoldNode;}}elseif(bt->right==NULL){if(bt->left==NULL){bt=NULL;oldNode=NULL;deleteoldNode;deletebt;}else{oldNode=NULL;bt=bt->left;bt->left=bt->left;deleteoldNode;}}else{BtreeNod*newNode=bt;oldNode=NULL;bt=bt->left;bt->left=bt->left;bt->right=bt->right;if(newNode->right!=NULL)bt->right->right=newNode->right;deleteoldNode;}}elseif(bt->data>a)del(bt->left,a);elsedel(bt->right,a);搜索功能。由于本实验中二叉树的节点数据只有一个，故查找的意义不大，只是遍历的一种重复，如果所有的数据均按照大小排列，例如使用insert()函数插入的节点，其搜索当前节点与查询节点的大小比较，若比当前节点大则向其右子树继续搜索，反之则向左子树搜索。主要代码如下:if(bt==NULL){cout<<"数据"<<a<<"未找到"<<endl;}elseif(bt->data==a){cout<<"数据"<<a<<"已找到"<<endl;}elseif(bt->data>a)find(bt->left,a);else