二叉排序树的创建、删除、插入等操作及二杈线索存储表示

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

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

2、序的主要流程图:主要模块：1)主函数模块Main(){建立n个关键字的二叉排序树并输出；从二叉树排序树T中删除任意结点，其关键字为key；在二叉树排序树T屮,插入一个结点t,关键字为key；在二义排序树T中递归查找关键字等于key2的数据元素；}2)创建二叉排序树模块BiTrccCrcatBST(intn){建立n个关键字的二义排序树；从键盘输入调建立n个关键字依次用TnsertBSTl(插入函数);返冋根结点T；输出过程；}1)删除模块DeleteNode(BiTree&T,intx){从二叉树排序树

3、T中删除任意结点，其关键字为x；可以实现删除根结点、叶子结点以及其它任意结点的功能；}2)插入模块voidInsertBSTl(BiTree&T,BiTNode*s){在二义树排序树T中,插入一个结点s(递归算法)；被CreatBST函数调用；}3)查找模块BiTreescarchBSTl(BiTreeT,TElcmTypckey){在根指针T所指二义排序树中递归查找关键字等于key的数据元素;若成功，返回指向该数据元素结点的指针；否则返冋空指针；}1•源程序代码：#include

4、usingnamespacestd;typedefintKeyType;typedefstructtree//声明树的结构{structtree*left;〃存放左子树的指针structtree*right;〃存放又子树的指针KeyTypekey;〃存放节点的内容}BSTNodc,*BSTrcc;〃声明二叉树的链表BSTreeinsertBST(BSTreetptr,KeyTypekey)//在二叉排序树中插入结点{〃若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回BSTrccf,p

5、=tptr;//p的初值指向根结点while(p)//查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲{if(p->key==key)〃树中已有key,无须插入returntptr;f=p；//f保存当前查找的结点，即f是p的双亲p=(kcykcy)?p->lcft:p->right;}p=(BSTree)malloc(sizeof(BSTNode));〃生成新结点p->key=key;p->left=p->right=NULL;if(tptr==NULL)//原树为空，新插入的结点

6、为新的根tptr=p;elseif(keykey)f->left=p;elsef->right=p;returntptr;}BSTreecreateBST()//建立二叉树{BSTreet=NULL;//根结点KeyTypekey;cin»key;while(key!=-l)t=insertBST(t.key);cin»key;returnt;voidinorder_btree(BSTreeroot)//中序遍历打印二叉排序树{BSTreep=root;if(p!=NULL){inordcr_b

7、trcc(p->lcft);cout«nM«p->key«nn;inorder_btree(p->right);}}intsearchBST(BSTreet,KeyTypekey)//查找{if(key==t->key)return1;if(t==NULL)return0;if(keykey)returnsearchBST(t->left,key);elsereturnsearchBST(t->right,key);}BSTreedeleteBST(BSTreetptr,KeyTypekey)/

8、/删除{BSTreep,tmp,parent=NULL;P=tptr;whilc(p){if(p->key==key)break;parent=p;p=(kcykcy)?p->lcft:p->right;}if(!p)returnNULL;tmp=p;if(!p->right&&!p->left)/*p的左右子树都为空*/{if(!parent)〃要删根，须修改根指针tptr=NULL;elseif(p==parent->right