文档章节

小蚂蚁学习数据结构(32)——二叉排序树的概念

嗜学如命的小蚂蚁
 嗜学如命的小蚂蚁
发布于 2016/02/07 19:37
字数 683
阅读 119
收藏 2

二叉排序树,定义:

    1,若左子树非空,则左子树上所有节点的关键字均小于根节点关键字。

    2,若右子树非空,则右子树上所有节点的关键字均大于根节点关键字。

    3,左右子树本身又是一颗二叉树。

    定义也是一个递归定义。

二叉排序树的特点:

    中序遍历二叉排序树,可以得到关键字序列是一个递增的有序序列。

二叉排序树查找思路:

    1,如果二叉排序树为空,则查找失败。

    2,如果key等于当前根节点,则查找成功。

    3,如果key小于当前根节点的值,在继续在根的左子树中查找。

    4,如果key大于当前根节点的值,在继续在根的右子树中查找。

二叉排序树的代码实现:

    (略),哈哈哈,今天是除夕,在家里心不静,就不写了,感觉也不难,以后有时间再写。

二叉排序树的查找:

    在二叉排序树上的平均查找长度与二叉树的形态有关。

    当树的形态比较均衡时,树的高度较小,平均查找长度也较小。

二叉排序树的插入:

    1,如果二叉排序树为空,则待插节点作为根节点插入空树中。

    2,如果待插入的关键字值和根节点关键字值相等,则无需插入。

    3,如果插入的关键字小于根节点的数值,则插入到左子树中。

    4,如果插入的关键字大于根节点的数值,则插入到右子树中。

    5,如此进行下去,当然,如果该数值已经存在就不再插入同一个数值。

二叉排序树的删除:

    1,删除叶子节点,很简单,直接删除,父节点的指针域赋予NULL

    2,删除单分支节点,将父节点与孩子节点直接相连

    3,删除双分子节点,用它的中序后继替换它,并使整棵树保持BST性质。

二叉排序树的查找分析:

    刚才也提到了,这个和二叉排序树的排列生成顺序有关,如果这个二叉排序树的形态是一条直线的话,这和顺序查找没有什么不同,为了防止这种情况的产生,就出来了一个平衡二叉树的概念。

平衡二叉树:

    略,马上晚会就开始了,PS:祝大家新年快乐,万事如意。 (*^-^*)


    学PHP的小蚂蚁 博客 http://my.oschina.net/woshixiaomayi/blog



© 著作权归作者所有

共有 人打赏支持
嗜学如命的小蚂蚁
粉丝 137
博文 161
码字总数 100864
作品 0
郑州
程序员
小蚂蚁学习数据结构(34)——平衡二叉树的概念

平衡二叉树的作用 由于二叉排序树的结构可能不平衡,导致对树的运算的时间复杂度增加。 调整二叉排序树的结构,使其始终成为平衡的状态——平衡二叉树。 平衡二叉树的定义 若一个二叉树中每个...

嗜学如命的小蚂蚁
2016/02/09
198
0
数据结构课程主页-2016级

  新学期,再度起程!   翻转的数据结构课程再度迎来新的一批同学。   前两年,资源建设基本完备,课堂方案逐渐完善,同学们对新型的学习方式设计给予了肯定(参见2014级问卷调查和201...

sxhelijian
2017/08/30
0
0
(转) 坚持完成这套学习手册,你就可以去 Google 面试了

C++ —— 不使用内建的数据类型。C++ —— 使用内建的数据类型,如使用 STL 的 std::list 来作为链表。Python —— 使用内建的数据类型(为了持续练习 Python),并编写一些测试去保证自己代...

wangxiaocvpr
2016/10/12
0
0
算法-数据结构

时间复杂度 O(log n) 意味着什么? 写给小白的时间复杂度指南 查找算法的 Java 实现 查找算法的 Java 实现 两个有序数组合并成一个有序数组 用拉链法和线性探测法解决哈希冲突 用拉链法和线性...

掘金官方
2017/12/14
0
0
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb
05/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

这些Spring中的设计模式,你都知道吗?

设计模式作为工作学习中的枕边书,却时常处于勤说不用的尴尬境地,也不是我们时常忘记,只是一直没有记忆。 Spring作为业界的经典框架,无论是在架构设计方面,还是在代码编写方面,都堪称行...

Java填坑之路
23分钟前
1
0
Spring Aop原理之Advisor过滤

在上文(Spring Aop之Advisor解析)中我们讲到,Spring Aop对目标bean的代理主要分为三个步骤:获取所有的Advisor,过滤当前bean可应用的Advisor和使用Advisor为当前bean生成代理对象,并且上文...

爱宝贝丶
34分钟前
0
0
JMockit学习教程

1 JMockit中文网 我觉得如果仅仅是开发自测的话,把JMockit中文网认真看一遍,就可以在项目中使用JMockit了。 http://jmockit.cn/index.htm 2 JMockit中文教程 官方文档中文版。对于不喜欢看...

SuperHeroes
46分钟前
0
0
Linux服务器几乎从不采用Arch Linux?

我们见得多的Linux服务器系统一般都是什么Ubuntu Server啊,什么Cent OS啊,什么Fedora啊,或者企业采用的Red Hat啊,为什么几乎没有Arch Linux呢?下面我将从若干个方面指出Arch Linux在服务...

linux-tao
57分钟前
0
0
js 函数柯里化 闭包

参考 https://mp.weixin.qq.com/s/GEHL3jarDdAAcr5tQGjmDg 一个统计求和的函数 需要知道整个数组的信息,然后遍历求值 function countMoney() { let money = 0 // 温馨提示:arguments...

阿豪boy
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部