数据结构——二叉搜索树.ppt
《数据结构——二叉搜索树.ppt》由会员分享,可在线阅读,更多相关《数据结构——二叉搜索树.ppt(38页珍藏版)》请在三一办公上搜索。
1、1/84,5 二叉树,2/84,5.1 二叉树的概念5.2 二叉树的周游5.3 二叉树的存储结构5.4 二叉搜索树5.5 堆与优先队列5.6 Huffman树及其应用5.7 二叉树知识点总结,主要内容,3/84,二叉搜索树,二叉搜索树二叉搜索树的查找 二叉搜索树的插入操作二叉搜索树的删除操作,二叉搜索树,一棵非空的二叉搜索树满足以下特征:每个结点都有一个作为搜索依据的关键码,所有结点的关键码互不相同。左子树(如果存在)上的所有结点的关键码均小于根结点的关键码。右子树(如果存在)上的所有结点的关键码均大于根结点的关键码。根结点的左右子树也都是二叉搜索树。,二叉搜索树又称为“二叉排序树”、“二叉查
2、找树”、“二叉检索树”,5/84,二叉搜索树举例,是二叉搜索树,是二叉搜索树,不是二叉搜索树,6/84,二叉搜索树的基本操作,查找插入删除,7/84,二叉搜索树查找操作,分割式查找法:若根结点的关键码等于查找的关键码,成功。否则,若小于根结点的关键码,查其左子树。大于根结点的关键码,查其右子树。,二叉搜索树的高效率在于继续检索时只需要查找两棵子树之一,8/84,如何查找元素 5?,查找成功!,二叉搜索树查找操作,9/84,二叉搜索树查找分析平均情况分析,15,60,70,30,20,50,ASL=(1+2+2+3+3+3)/6=14/6,ASL=(1+2+3+4+5+6)/6=21/6,10/
3、84,二叉搜索树插入操作,首先执行查找算法,找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意:新插入的结点总是叶子结点。,11/84,利用插入操作可以构造一棵二叉搜索树,二叉搜索树插入操作,12/84,二叉搜索树插入操作(另一个例子),对于关键码集合K=50,19,35,55,20,5,100,52,88,53,92二叉搜索树的生成过程如图所示:,13/84,对二叉搜索树的检索,每一次只需与结点的一棵子树相比较在执行插入操作时,也不必像在有序线性表中插入元素那样要移动大量的数据,而只需改动某个结点的空指针插入一个
4、叶结点即可与查找结点的操作一样,插入一个新结点操作的时间复杂度是根到插入位置的路径长度,因此在树形比较平衡时二叉搜索树的效率相当高,14/84,二叉搜索树删除操作情况1,叶子结点:直接删除,更改它的父亲结点的相应指针场为空。如:删除值为 15、70 的结点。,15,60,70,30,20,50,子树的根结点:若被删结点的左儿子为空或者右儿子为空。如何处理呢?,15/84,二叉搜索树删除操作情况2,122,250,300,110,200,99,105,230,400,450,500,子树的根结点:若被删结点的左儿子为空或者右儿子为空。如删除结点的关键值为 99 结点。,16/84,要删除的节点有
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 二叉 搜索
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-3787975.html