二叉排序树的创建、删除、插入等操作

《二叉排序树的创建、删除、插入等操作》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机科学与工程学院武汉工程大学计算机科学与工程学院《数据结构》实验报告专业班级09计算机工程01实验地点419学生学号0905080116指导教师蔡琼学生姓名沈亮实验时间实验项目查找技术综合应用实验类别操作性（）验证性（）设计性（）综合性（Y）其它（）实验目的及要求（1）熟练掌握查找的常用算法；（2）熟练设计和应用查找算法解决比较简单的实际问题。成绩评定表类别评分标准分值得分合计上机表现积极出勤、遵守纪律认真完成实验任务30分报告质量程序代码规范、功能正确填写内容完整、体现收获70分说明：评阅教师：日期：年月日13数据结构上机实验计算机科学与工程学院实验内容：二叉排序

2、树。任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。实验说明：二叉排序树存储结构如下：typedefstructBiTNode{//结点结构structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;二叉排序树插入算法伪代码如下：1.若root是空树，则将结点s作为根结点插入；否则2.若s->data＜root->data，则把结点s插入到root的左子树中；否则3.把结点s插入到root的右子树中。二叉排序树中删除一个结点f的左孩子结点p算法伪代码如下：1.若结点p是叶子，则直接删除结

3、点p；2.若结点p只有左子树，则只需重接p的左子树；若结点p只有右子树，则只需重接p的右子树；3.若结点p的左右子树均不空，则3.1查找结点p的右子树上的最左下结点s以及结点s的双亲结点par；3.2将结点s数据域替换到被删结点p的数据域；3.3若结点p的右孩子无左子树，则将s的右子树接到par的右子树上；否则，将s的右子树接到结点par的左子树上；3.4删除结点s；13数据结构上机实验计算机科学与工程学院1.实验分析：程序的主要流程图：否是开始建树：①依次输入n个关键字②插入二叉排序树中③中序输出创建过程删除任意结点插入一个结点查找关键字中序输出操作后二叉排序树是否继

4、续结束主要模块：1）主函数模块Main(){建立n个关键字的二叉排序树并输出；从二叉树排序树T中删除任意结点,其关键字为key；在二叉树排序树T中，插入一个结点t,其关键字为key；在二叉排序树T中递归查找关键字等于key2的数据元素；}2）创建二叉排序树模块BiTreeCreatBST(intn){建立n个关键字的二叉排序树；从键盘输入调建立n个关键字依次用InsertBST1（插入函数）；返回根结点T；13数据结构上机实验计算机科学与工程学院输出过程；}3）删除模块DeleteNode(BiTree&T,intx){从二叉树排序树T中删除任意结点,其关键字为x；可以

5、实现删除根结点、叶子结点以及其它任意结点的功能；}4）插入模块voidInsertBST1(BiTree&T,BiTNode*s){在二叉树排序树T中，插入一个结点s(递归算法)；被CreatBST函数调用；}5）查找模块BiTreesearchBST1(BiTreeT,TElemTypekey){在根指针T所指二叉排序树中递归查找关键字等于key的数据元素；若成功，返回指向该数据元素结点的指针；否则返回空指针；}13数据结构上机实验计算机科学与工程学院2.源程序代码：#includeusingnamespacestd;typedefintKeyT

6、ype;typedefstructtree//声明树的结构{structtree*left;//存放左子树的指针structtree*right;//存放又子树的指针KeyTypekey;//存放节点的内容}BSTNode,*BSTree;//声明二叉树的链表BSTreeinsertBST(BSTreetptr,KeyTypekey)//在二叉排序树中插入结点{//若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回BSTreef,p=tptr;//p的初值指向根结点while(p)//查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲{if(

7、p->key==key)//树中已有key，无须插入returntptr;f=p;//f保存当前查找的结点，即f是p的双亲p=(keykey)?p->left:p->right;}p=(BSTree)malloc(sizeof(BSTNode));//生成新结点p->key=key;p->left=p->right=NULL;if(tptr==NULL)//原树为空，新插入的结点为新的根tptr=p;elseif(keykey)f->left=p;elsef->right=p;returntptr;}BSTreecreat