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

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

1、安徽工程大学计算机与信息学院课程设计报告课程名称《数据结构》课题名称二叉排序树的创建、删除、插入操作专业计算机科学与技术班级计算机121班学号姓名殷世军联系方式指导教师姚红燕实验内容：二叉排序树。任意给定一组数据，设计一个算法，建立一棵二叉排序树，对它进行查找、插入、删除等操作。实验说明：二叉排序树存储结构如下：typedefstructBiTNode{//结点结构structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;二叉排序树插入算法伪代码如下：1.若root是

2、空树，则将结点s作为根结点插入；否则2.若s->data＜root->data，则把结点s插入到root的左子树中；否则3.把结点s插入到root的右子树中。二叉排序树中删除一个结点f的左孩子结点p算法伪代码如下：1.若结点p是叶子，则直接删除结点p；2.若结点p只有左子树，则只需重接p的左子树；若结点p只有右子树，则只需重接p的右子树；3.若结点p的左右子树均不空，则3.1查找结点p的右子树上的最左下结点s以及结点s的双亲结点par；3.2将结点s数据域替换到被删结点p的数据域；3.3若结点p的右孩子无左子树，则将

3、s的右子树接到par的右子树上；否则，将s的右子树接到结点par的左子树上；3.4删除结点s；1.实验分析：程序的主要流程图：否是开始建树：①依次输入n个关键字②插入二叉排序树中③中序输出创建过程删除任意结点插入一个结点查找关键字中序输出操作后二叉排序树是否继续结束主要模块：1）主函数模块Main(){建立n个关键字的二叉排序树并输出；从二叉树排序树T中删除任意结点,其关键字为key；在二叉树排序树T中，插入一个结点t,其关键字为key；在二叉排序树T中递归查找关键字等于key2的数据元素；}2）创建二叉排序树模块B

4、iTreeCreatBST(intn){建立n个关键字的二叉排序树；从键盘输入调建立n个关键字依次用InsertBST1（插入函数）；返回根结点T；输出过程；}3）删除模块DeleteNode(BiTree&T,intx){从二叉树排序树T中删除任意结点,其关键字为x；可以实现删除根结点、叶子结点以及其它任意结点的功能；}4）插入模块voidInsertBST1(BiTree&T,BiTNode*s){在二叉树排序树T中，插入一个结点s(递归算法)；被CreatBST函数调用；}5）查找模块BiTreesearchB

5、ST1(BiTreeT,TElemTypekey){在根指针T所指二叉排序树中递归查找关键字等于key的数据元素；若成功，返回指向该数据元素结点的指针；否则返回空指针；}2.源程序代码：#includeusingnamespacestd;typedefintKeyType;typedefstructtree//声明树的结构{structtree*left;//存放左子树的指针structtree*right;//存放又子树的指针KeyTypekey;//存放节点的内容}BSTNode,*BSTr

6、ee;//声明二叉树的链表BSTreeinsertBST(BSTreetptr,KeyTypekey)//在二叉排序树中插入结点{//若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回BSTreef,p=tptr;//p的初值指向根结点while(p)//查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲{if(p->key==key)//树中已有key，无须插入returntptr;f=p;//f保存当前查找的结点，即f是p的双亲p=(keykey)?p->left:p->rig

7、ht;}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;}BSTreecreateBST()//建立二叉树{BSTreet=NULL;//根结点KeyTypekey;cin>>key;while(key!=-1){t=insertBST(

8、t,key);cin>>key;}returnt;}voidinorder_btree(BSTreeroot)//中序遍历打印二叉排序树{BSTreep=root;if(p!=NULL){inorder_btree(p->left);cout<<""<key<<"";inorder_btree(p->right);}}intsearch