文档章节

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

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

二叉排序树,定义:

    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



© 著作权归作者所有

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

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

嗜学如命的小蚂蚁 ⋅ 2016/02/09 ⋅ 0

数据结构课程主页-2016级

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

sxhelijian ⋅ 2017/08/30 ⋅ 0

算法-数据结构

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

掘金官方 ⋅ 2017/12/14 ⋅ 0

(转) 坚持完成这套学习手册,你就可以去 Google 面试了

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

wangxiaocvpr ⋅ 2016/10/12 ⋅ 0

一文掌握关于Java数据结构所有知识点(欢迎一起完善)

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

snailclimb ⋅ 05/08 ⋅ 0

小蚂蚁学习数据结构(17)——树、二叉树性质、储存方式

树 是一类非线性数据结构,是以分支关系定义的层次结构。 特点: 至少有一个节点——根,只有根的树成为最小树 树中各子树是互不相交的集合 术语(略) 二叉树 特点: 每个节点最多有二颗子树...

嗜学如命的小蚂蚁 ⋅ 2016/01/17 ⋅ 0

数据结构(二)——树结构模型及应用

基于树实现的数据结构,具有两个核心特征: 逻辑结构:数据元素之间具有层次关系; 数据运算:操作方法具有Log级的平均时间复杂度。 因此,树在文件系统、编译器、索引以及查找算法中有很广的...

yhthu ⋅ 2017/11/11 ⋅ 0

白话经典算法系列之七 堆与堆排序

堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。 二叉堆的定义 二叉堆是完全二叉树或者是近似完全二叉树。...

长平狐 ⋅ 2012/12/10 ⋅ 0

白话经典算法系列之七 堆与堆排序

堆排序与快速排序,归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的二叉堆。 二叉堆的定义 二叉堆是完全二叉树或者是近似完全二叉树。...

彭博 ⋅ 2012/04/12 ⋅ 0

平衡二叉树、完全二叉树、满二叉树、二叉搜索(查找 / 排序)树、平衡二叉搜索树、二叉堆

查了一些博客、百科整理出以下关于树的定义以及易混点: 平衡二叉树:一棵空树或左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是平衡二叉树。(注意:实际应用中很少有不是二叉搜...

BeerBread134 ⋅ 2017/06/03 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

服务网关过滤器

过滤器作用 我们的微服务应用提供的接口就可以通过统一的API网关入口被客户端访问到了。但是,每个客户端用户请求微服务应用提供的接口时,它们的访问权限往往都需要有一定的限制,系统并不会...

明理萝 ⋅ 11分钟前 ⋅ 1

【2018.06.21学习笔记】【linux高级知识 14.1-14.3】

14.1 NFS介绍 NFS服务全称是NetWork File System:网络文件系统,最早有sun公司开发的,4.0版本由Netapp公司开发,是基于RPC远程过程调用(Remote Procedure Call)协议的服务。 14.2 NFS服务...

lgsxp ⋅ 19分钟前 ⋅ 0

Day18 vim编辑模式、命令模式与练习

编辑模式 命令模式 :nohl 不高亮显示 :x与:wq类似,如果在更改文件之后操作,两者效果一样;如果打开文件,没有任何操作; :wq会更改mtime,但是:x不会。 练习题 扩展 vim的特殊用法 ht...

杉下 ⋅ 23分钟前 ⋅ 0

Enum、EnumMap、EnumSet

1、Enum 不带参数 public enum Car { AUDI { @Override public int getPrice() { return 25000; } }, MERCEDES { ......

职业搬砖20年 ⋅ 24分钟前 ⋅ 0

Java中的锁使用与实现

1.Lock接口 锁是用来控制多个线程访问共享资源的方式,一般来说,一个锁能够防止多个线程同时访问共享资源。 在Lock出现之前,java程序是靠synchronized关键字实现锁功能的,而Java SE5之后,...

ZH-JSON ⋅ 25分钟前 ⋅ 0

线程组和 ThreadLocal

前言 在上面文章中,我们从源码的角度上解析了一下线程池,并且从其 execute 方法开始把线程池中的相关执行流程过了一遍。那么接下来,我们来看一个新的关于线程的知识点:线程组。 线程组 ...

猴亮屏 ⋅ 26分钟前 ⋅ 0

相对路径和绝对路径

基本概念   文件路径就是文件在电脑中的位置,表示文件路径的方式有两种,相对路径和绝对路径。在网页设计中通过路径可以表示链接,插入图像、Flash、CSS文件的位置。   物理路径:物理路...

临江仙卜算子 ⋅ 30分钟前 ⋅ 0

消息队列属性及常见消息队列介绍

什么是消息队列? 消息队列是在消息的传输过程中保存消息的容器,用于接收消息并以文件的方式存储,一个队列的消息可以同时被多个消息消费者消费。分布式消息服务DMS则是分布式的队列系统,消...

中间件小哥 ⋅ 32分钟前 ⋅ 0

java程序员使用web3j进行以太坊开发详解

如何使用web3j为Java应用或Android App增加以太坊区块链支持,教程内容即涉及以太坊中的核心概念,例如账户管理包括账户的创建、钱包创建、交易转账,交易与状态、智能合约开发与交互、过滤器...

笔阁 ⋅ 33分钟前 ⋅ 0

vim编辑模式、vim命令模式

vim编辑模式 使用vim filename 进入的界面是一般模式,在这个模式下虽然我们能够查看,复制,剪切,粘贴,但是不能编辑新的内容,如何能直接写入东西呢?这就需要进入编辑模式了,从一般模式...

李超小牛子 ⋅ 35分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部