文档章节

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

嗜学如命的小蚂蚁
 嗜学如命的小蚂蚁
发布于 2016/02/07 19:37
字数 683
阅读 120
收藏 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



© 著作权归作者所有

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

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

嗜学如命的小蚂蚁
2016/02/09
198
0
算法-数据结构

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

掘金官方
2017/12/14
0
0
数据结构课程主页-2016级

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

sxhelijian
2017/08/30
0
0
JavaScript实现简单二叉查找树

前两天接到了蚂蚁金服的面试电话,面试官很直接,上来就抛出了三道算法题。。。 其中有一道关于二叉树实现中序遍历的,当时没回答好,所以特意学习了一把二叉树的知识,行文记录总结。 二叉树...

行无忌
08/03
0
0
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

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

snailclimb
05/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

各种开源汇编、反汇编引擎的非专业比较

由于平时业余兴趣和工作需要,研究过并使用过时下流行的各种开源的x86/64汇编和反汇编引擎。如果要对汇编指令进行分析和操作,要么自己研究Intel指令集写一个,要么就用现成的开源引擎。自己...

simpower
8分钟前
1
0
(4)添加vue-router

(4)添加vue-router 1 安装vue-router cnpm install vue-router --save 2 页面准备 新建目录/src/views/common,此目录下面建立4个组件404.vue、home.vue、login.vue、theme.vue。每个文件...

neumeng
10分钟前
1
0
高可用性系统在大众点评的实践与经验

背景 所谓高可用性指的是系统如何保证比较高的服务可用率,在出现故障时如何应对,包括及时发现、故障转移、尽快从故障中恢复等等。本文主要以点评的交易系统的演进为主来描述如何做到高可用...

Skqing
18分钟前
2
0
Network protocols

The network stack does serveral seemingly-impossible things. It does reliable transmission over our unreliable networks, usually without any detactable hiccups. It adapts smooth......

nao
19分钟前
1
0
Android 生命周期方法

1,onCreate(); 2,onStart(); 3,onResume(); //打开页面,前三个方法自动执行 4,onPause(); 5,onStop(); //打开其他页面,前一个页面执行这俩方法 6,onRestart(); //onStart(),onResume //当关闭...

lanyu96
26分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部