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

计算机科学与工程学院

《数据结构》实验报告

专业班级 学生学号 学生姓名 实验项目 实验类别 09计算机工程01 0905080116 沈亮 实验地点 指导教师 实验时间 查找技术综合应用 操作性（）验证性（ ）设计性（ ）综合性（Y ）其它（ ） 419 蔡琼 求 实验目的及要（1）熟练掌握查找的常用算法； （2）熟练设计和应用查找算法解决比较简单的实际问题。 成 绩 评 定 表 类 别 上机表现 报告质量 说明： 评 分 标 准 积极出勤、遵守纪律 认真完成实验任务 程序代码规范、功能正确 填写内容完整、体现收获 分值 30分 70分 得分 合 计 评阅教师： 日 期： 年 月 日 实验内容：二叉排序树。 任意给定一组数据.设计一个算法.建立一棵二叉排序树.对它进行查找、插入、删除等操作。 实验说明： 二叉排序树存储结构如下： typedef struct BiTNode { // 结点结构 struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; 二叉排序树插入算法伪代码如下： 1. 若root是空树，则将结点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的右孩子无左子树，则将s的右子树接到par的右子树上； 否则，将s的右子树接到结点par的左子树上； 3.4 删除结点s； . .

1.实验分析： 程序的主要流程图： 开始 建树： ① 依次输入n个关键字 ② 插入二叉排序树中 ③ 中序输出创建过程 删除任意结点 插入一个结点 查找关键字 中序输出操作后二叉排序树 是否继续 否 结束 是 主要模块： 1）主函数模块 Main() { 建立n个关键字的二叉排序树并输出； 从二叉树排序树T中删除任意结点,其关键字为key； 在二叉树排序树T中.插入一个结点t,其关键字为key； 在二叉排序树T中递归查找关键字等于 key2 的数据元素； } 2）创建二叉排序树模块 BiTree CreatBST(int n) { 建立n个关键字的二叉排序树； 从键盘输入调建立n个关键字依次用InsertBST1（插入函数）； 返回根结点T； . .

输出过程； } 3）删除模块 DeleteNode(BiTree &T, int x) { 从二叉树排序树T中删除任意结点,其关键字为x； 可以实现删除根结点、叶子结点以及其它任意结点的功能； } 4）插入模块 void InsertBST1(BiTree &T,BiTNode *s) { 在二叉树排序树T中.插入一个结点s(递归算法)； 被CreatBST函数调用； } 5）查找模块 BiTree searchBST1(BiTree T,TElemType key) { 在根指针T所指二叉排序树中递归查找关键字等于 key 的数据元素； 若成功.返回指向该数据元素结点的指针； 否则返回空指针； } . .

2.源程序代码： #include using namespace std; typedef int KeyType; typedef struct tree//声明树的结构 { struct tree *left; //存放左子树的指针 struct tree *right; //存放又子树的指针 KeyType key; //存放节点的内容 } BSTNode, * BSTree; //声明二叉树的链表 BSTree insertBST(BSTree tptr,KeyType key)// 在二叉排序树中插入结点 { //若二叉排序树tptr中没有关键字为key的结点.则插入.否则直接返回 BSTree f,p=tptr; //p的初值指向根结点 while(p) //查找插入位置.循环结束时.p是空指针.f指向待插入结点的双亲 { if(p->key==key) //树中已有key.无须插入 return tptr; 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; else if(keykey) f->left=p; else f->right=p; return tptr; } BSTree createBST()//建立二叉树 { BSTree t=NULL; //根结点 KeyType key; cin>>key; while(key!=-1) { t=insertBST(t,key); cin>>key; } . .

return t; } void inorder_btree(BSTree root)// 中序遍历打印二叉排序树 { BSTree p=root; if(p!=NULL){ inorder_btree(p->left ); cout<<\" \"<key<<\" \"; inorder_btree(p->right ); } } int searchBST(BSTree t,KeyType key)//查找 { if(key==t->key) return 1; if(t==NULL) return 0; if(keykey) return searchBST(t->left,key); else return searchBST(t->right,key); } BSTree deleteBST(BSTree tptr,KeyType key)//删除 { BSTree p,tmp,parent=NULL; p=tptr; while(p) { if(p->key==key) break; parent=p; p=(keykey)?p->left:p->right; } if(!p) return NULL; tmp=p; if(!p->right&&!p->left) /*p的左右子树都为空*/ { if(!parent) //要删根.须修改根指针 tptr=NULL; else if(p==parent->right) parent->right=NULL; else parent->left=NULL; free(p); } . .

else if(!p->right) //p的右子树为空.则重接p的左子树 { p=p->left; if(!parent) //要删根.须修改根指针 tptr=p; else if(tmp==parent->left) parent->left=p; else parent->right=p; free(tmp); } else if(!p->left) //的左子树为空.则重接p的左子树 { p=p->right; if(!parent) //要删根.须修改根指针 tptr=p; else if(tmp==parent->left) parent->left=p; else parent->right=p; free(tmp); } else if(p->right&&p->left) //p有左子树和右子树.用p的后继覆盖p然后删去后继 { //另有方法：用p的前驱覆盖p然后删去前驱||合并p的左右子树 parent=p; //由于用覆盖法删根.则不必特殊考虑删根 p=p->right; while(p->left) { parent=p; p=p->left; } tmp->key=p->key; if(p==parent->left) parent->left=NULL; else parent->right=NULL; free(p); } return tptr; } int main() { KeyType key; . .

int flag,test; char cmd; BSTree root; do { cout<<\"\\n\\n\"<>cmd; flag++; }while(cmd!='c'&&cmd!='C'&&cmd!='a'&&cmd!='A'); if(cmd=='c'||cmd=='C') { cout<<\"请输入你所要创建的二叉树的结点的值.以-1结束：\\n\"; root=createBST(); do { flag=0; cout<<\"\\n\\n中序遍历二叉树：\"<cout<<\"\\***********************************************************\"<>key; test=searchBST(root,key); if(test==0) cout<<\"\\n对不起.你所查找的结点 \"<>key; root=insertBST(root,key); //注意必须将值传回根 break; case 'd': case 'D': cout<<\"请输入你要删除结点的关键字：\\n\"; cin>>key; root=deleteBST(root,key); //注意必须将值传回根 if(root==NULL) cout<<\"\\n对不起.你所删除的结点 \"<} 实 验 内 容 . .

3.测试用例： 1,程序运行时菜单显示如下： 当输入的二叉树序列为：{2,6,9,8,4}时.创建二叉排序树.并输出结果如下： 1.查找9结点时.运行结果如下： . .

2.删除结点6时运行结果如下： 3.插入结点7时运行结果如下： . .

实 验 内 容 . .

4.实验总结： 通过这次的实验.我认识到：仅仅掌握课本上的知识是不够的.在实际操作时.常常遇到一些问题.自己看不懂.更无法解决。不过.经过自己不断的思考.尝试着去更改代码中出现的问题。虽然开始很困难.但在老师和同学的帮助下.我逐渐的熟悉了许多操作.为后继工作的顺利进行做了准备。 个人的力量是薄弱的.我学会了咨询别人.不再胆怯.不再保守。 在过程中和同学相互讨论.询问老师.不断进步。 也许.我们可以说.编一个程仅仅是开始.调试和运行相比之下更难。实践中收获的远比想象的多。 看到自己完成了所要求的任务.有一种无法用言语来形容的欣慰之感.这也是无法从学习书本知识中得到的。

. .