二叉搜索树(BinarySearchTree)课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《二叉搜索树(BinarySearchTree)课件.ppt》由用户(ziliao2023)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 搜索 BinarySearchTree 课件
- 资源描述:
-
1、1 1二叉搜索树二叉搜索树 (Binary Search Tree)(Binary Search Tree)n定义定义 二叉搜索树或者是一棵空树,或者是具二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树:有下列性质的二叉树:每个结点都有一个作为搜索依据的关键每个结点都有一个作为搜索依据的关键码码(key),所有结点的关键码互不相同。,所有结点的关键码互不相同。左子树(如果非空)上所有结点的关键左子树(如果非空)上所有结点的关键码都小于根结点的关键码。码都小于根结点的关键码。右子树(如果非空)上所有结点的关键右子树(如果非空)上所有结点的关键码都大于根结点的关键码。码都大于根结点的关键码。左
2、子树和右子树也是二叉搜索树。左子树和右子树也是二叉搜索树。2 2351545504025102030二叉搜索树例二叉搜索树例n结点左子树上所结点左子树上所有关键码小于结有关键码小于结点关键码;点关键码;n右子树上所有关右子树上所有关键码大于结点关键码大于结点关键码;键码;n注意:若从根结点到某个叶结点有一条路径,注意:若从根结点到某个叶结点有一条路径,路径左边的结点的关键码不一定小于路径上路径左边的结点的关键码不一定小于路径上的结点的关键码。如箭头所示路径。的结点的关键码。如箭头所示路径。3 3n性质性质:如果对一棵二叉搜索树进行中序如果对一棵二叉搜索树进行中序遍历,可以按从小到大的顺序,将各
3、结遍历,可以按从小到大的顺序,将各结点关键码排列起来,所以也称二叉搜索点关键码排列起来,所以也称二叉搜索树为树为二叉排序树二叉排序树(BST)。n二叉搜索树的类定义二叉搜索树的类定义 略略n二叉搜索树的类定义用二叉链表作为它二叉搜索树的类定义用二叉链表作为它的存储表示,许多操作的实现与二叉树的存储表示,许多操作的实现与二叉树类似。类似。4 4二叉搜索树的搜索算法二叉搜索树的搜索算法n在二叉搜索树上进行搜索,是一个在二叉搜索树上进行搜索,是一个从根结点开从根结点开始始,沿某一个分支逐层向下沿某一个分支逐层向下进行比较判等的过进行比较判等的过程。它可以是一个递归的过程。程。它可以是一个递归的过程。
4、n假设想要在二叉搜索树中搜索关键码为假设想要在二叉搜索树中搜索关键码为 x 的元的元素,搜索过程从根结点开始。素,搜索过程从根结点开始。n如果如果根指针为根指针为NULL,则,则搜索不成功搜索不成功;否则用;否则用给定值给定值 x 与根结点的关键码进行比较:与根结点的关键码进行比较:若若给定值等于根结点关键码给定值等于根结点关键码,则,则搜索成功搜索成功,返回搜索成功信息并报告搜索到结点地址。返回搜索成功信息并报告搜索到结点地址。5 5 若给定值小于根结点的关键码,则继续若给定值小于根结点的关键码,则继续递归搜索根结点的左子树;递归搜索根结点的左子树;否则。递归搜索根结点的右子树。否则。递归搜
5、索根结点的右子树。搜索搜索45搜索成功搜索成功搜索搜索28搜索失败搜索失败3515455040251020306 6BSTNode*Search(T x,BSTNode*subtree)/递归算法:在以 subtree 为根的二叉搜索树中/搜索含 x 的结点。若找到,则函数返回该结点/的地址,否则函数返回 NULL 值。if(subtree=NULL)return NULL;else if(x data)return Search(x,subtree-left);else if(x subtree-data)return Search(x,subtree-right);else return
6、subtree;/搜索成功7 7BSTNode*Search(T x,BSTNode*subtree)/迭代算法:在当前以 subtree 为根的二叉搜索/树中搜索含 x 的结点。若找到,则函数返回该/结点的地址,否则函数返回 NULL 值。while(subtree!=NULL)if(x=subtree-data)return subtree;if(x data)subtree=subtree-left;else subtree=subtree-right;return NULL;8 8n搜索过程是从根结点开始,沿某条路径自上而搜索过程是从根结点开始,沿某条路径自上而下逐层比较判等的过程。下
7、逐层比较判等的过程。n搜索成功,搜索指针将停留在树上某个结点;搜索成功,搜索指针将停留在树上某个结点;搜索不成功,搜索指针将走到树上某个结点的搜索不成功,搜索指针将走到树上某个结点的空子树。空子树。n设树的高度为设树的高度为 h,最多比较次数不超过,最多比较次数不超过 h。9 9二叉搜索树的插入算法二叉搜索树的插入算法n为了向二叉搜索树中插入一个新元素,必须为了向二叉搜索树中插入一个新元素,必须先检查这个元素是否在树中已经存在先检查这个元素是否在树中已经存在。n在插入之前,先使用搜索算法在树中检查要在插入之前,先使用搜索算法在树中检查要插入的元素在不在树中。插入的元素在不在树中。如果搜索成功,
8、说明树中已经有这个元素,如果搜索成功,说明树中已经有这个元素,不再插入;不再插入;如果搜索不成功,说明树中原来没有关键如果搜索不成功,说明树中原来没有关键码等于给定值的结点,把新元素加到搜索码等于给定值的结点,把新元素加到搜索操作停止的地方。操作停止的地方。1010插入新结点插入新结点 28二叉搜索树的插入二叉搜索树的插入n每次结点的插入,都要每次结点的插入,都要从根结点出发搜索插入从根结点出发搜索插入位置,然后把新结点作位置,然后把新结点作为叶结点插入。为叶结点插入。3515455040251020302811 11二叉搜索树的插入算法二叉搜索树的插入算法bool Insert(T e,BS
9、TNode&subtree)/递归算法:在以 subtree 为根的二叉搜索树中插入/值为 e 的结点。若树中已有结点 e,则不插入 if(subtree=NULL)/新结点作为叶结点插入 subtree=new BSTNode(e);/创建新结点 return true;else if(e data)Insert(e,subtree-left);else if(e subtree-data)Insert(e,subtree-right);1212n注意参数表中引用型指针参数注意参数表中引用型指针参数subtree的的使用。使用。n利用二叉搜索树的插入算法,可以很方利用二叉搜索树的插入算法,可
展开阅读全文