文档章节

小蚂蚁学习数据结构(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



© 著作权归作者所有

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

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

嗜学如命的小蚂蚁
2016/02/09
198
0
算法与数据结构(五)树表的查找

树表的查找 (1)二叉排序树 (2)二叉排序树的操作——查找 (3)二叉排序树的操作——插入 (4)二叉排序树的操作——生成 (5)二叉排序树的操作——删除 (1)二叉排序树 由于线性表的查...

OrdinaryMan
12/01
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
数据结构课程主页-2016级

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

sxhelijian
2017/08/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

mac 下 mysql 8.0.13 安装并记录遇到的问题 以便以后查看

安装 官网mysql 下载地址 安装过程 省去 安装好之后 下载navicat 错误1 链接 遇到 mysql 2003 - Can't connect to MySQL server 错误, 解决方案 重启mysql 服务 #错误2 ERROR 1045: Acces...

杭州-IT攻城狮
23分钟前
3
0

中国龙-扬科
26分钟前
1
0
[Spring4.x]基于spring4.x纯注解的Web工程搭建

在前文中已经说明了如何基于 Spring4.x+ 版本开发纯注解的非web项目,链接如下: https://my.oschina.net/morpheusWB/blog/2985600 本文则主要说明,如何在Web项目中,"基于spring纯注解方式...

morpheusWB
55分钟前
13
0
基础编程题目集-7-13 日K蜡烛图

股票价格涨跌趋势,常用蜡烛图技术中的K线图来表示,分为按日的日K线、按周的周K线、按月的月K线等。以日K线为例,每天股票价格从开盘到收盘走完一天,对应一根蜡烛小图,要表示四个价格:开...

niithub
今天
5
0
Jenkins window 下的安装使用

1.下载:https://jenkins.io/download/ 双击安装完毕,将自动打开浏览器: http://localhost:8080 打开对应位置的文件,将初始密钥粘贴至输入框。 第一个是 安装默认的软件;第二个是 自定义...

狼王黄师傅
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部