排序二叉树

排序二叉树排序二叉树一、基本概念二叉树是一种从上往下的树状结构的数据结构,从根节点开始每个节点最多有两个子节点,左边的为左子节点,右边的为右子节点。排序二叉树–有顺序,且没有重复元素的二叉树。顺序为:

大家好,又见面了,我是你们的朋友全栈君。

排序二叉树

一、基本概念

二叉树是一种从上往下的树状结构的数据结构,从根节点开始每个节点最多有两个子节点,

左边的为左子节点,右边的为右子节点。

排序二叉树–有顺序且没有重复元素的二叉树。顺序为:

对每个节点而言:

1)如果左子树不为空,则左子树上的所有节点都小于该节点;

2)如果右子树不为空,则右子树上的所有节点都大于该节点;

<span role="heading" aria-level="2">排序二叉树

如图,根节点为5,左边的节点都大于5,右边的节点都小于5。

二、基本算法

1.查找

1)首先与根节点比较,相同则找到;

2)如果小于根节点,则到左子树种递归查找;

3)如果大于根节点,则到右子树中递归查找;

这个步骤与在数组中进行二分查找是类似的。此外,在排序二叉树中查找最大值和最小值很简单。

2.遍历

排序二叉树可以方便的按序遍历,用递归的方式。

如下图的例子,先访问根节点的左子树,一直到最左边的节点–1,1没有右子树

,返回上一层,访问3,然后访问3的右子树,4没有左子树,所以访问4,然后4的右

子树6,以此类推。1–3–4–6–7–8–9

<span role="heading" aria-level="2">排序二叉树

 

 不用递归的方式,也可以实现按序遍历:第一个节点为最左边的节点,从第一个

节点开始,依次找后继节点,找其后继节点的算法为:

1)如果该节点有右子节点,则后继节点为右子树中的最小节点;

2)如果该节点无右子节点,则后继节点为父节点或者某个祖先节点,

从当前节点往上找,如果它是父节点的右孩子,则继续找父节点,直到

它不是右孩子或父节点为空,第一个非右孩子节点的父节点就是后继节点,

如果找不到这样的祖先节点,则后继为空,遍历结束。

3.插入

在排序二叉树中,插入元素首先要找插入位置,即新节点的父节点。

与查找元素类似从根节点开始找:

1)与当前节点相同,则已经存在了,不能插入;

2)如果小于当前节点,则到左子树中查找,如果左子树为空,则当前节点为要找到的父节点;

3)如果大于当前节点则到右子树中查找,如果右子树为空,则当前节点为要找的父节点。

 3.删除

从排序二叉树中删除一个节点,主要有三种情况:

1)节点为叶子节点: 直接删除

2)节点只有一个孩子节点:

删除当前节点,让其子节点与父节点建立链接。

 <span role="heading" aria-level="2">排序二叉树

3)节点有两个孩子节点:

<span role="heading" aria-level="2">排序二叉树

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/154662.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Unity3D学习路线与学习经验分享[通俗易懂]

    Unity3D学习路线与学习经验分享[通俗易懂]Unity3D学习路线与学习经验分享//最后一次更新为2019.7.22日,更新了一些废掉的链接作者:15游02丁祺你好,这篇文档是我的导师孙老师(以下简称老孙)指名我书写给新手、初学者以及技能有些许缺陷的人的一篇经验分享的文档,当然如果你看到了这些文字,代表着你是一个有意愿或期望去学习这款软件的人。因人与人之间有很多的不同,以下我会尽我所能,通过不同切入点与角度,并根据以上人群的不同…

  • ppsspp文件格式_pps文件用什么打开

    ppsspp文件格式_pps文件用什么打开MP4文件介绍mp4文件由box组成,每个box分为Header和Data。其中Header部分包含了box的类型和大小,Data包含了子box或者数据,box可以嵌套子box。下图是一个典型mp4文件的基本结构:box结构AVCDecoderConfiguration(AvcC)语法(解析sps、pps)aligned(8)classAVCDecoderConfigurationRecord{unsignedint(8)configurationVersion=1;unsig

    2022年10月10日
  • Java创建二维数组

    Java创建二维数组1、Java创建二维数组:int[][]array=newint[6][6];2、直接创建二维数组并赋值:int[][]array={{1,2,3},{1,2,3},{1,2,3}};3、二维数组的声明:先声明再分配内存数组声明:数据类型数组名[][];…

  • POENIX的BIOS报警声

    POENIX的BIOS报警声

  • TinyXML2使用方法及示例

    TinyXML2使用方法及示例转自https://blog.csdn.net/liang_baikai/article/details/78783839概述 TinyXML2是简单实用的开源的C++XML文件解析库,可以很方便的应用到现有的项目之中。  TinyXML2解析器相对TinyXML1在代码上是完全重写,使其更适合于游戏开发中使用。它使用更少的内存,更快,并使用更少的内存分配。说明 xml类似数据库,…

  • jdbctemplate常用方法_cannot create jdbc driver of

    jdbctemplate常用方法_cannot create jdbc driver of/*StreamTypeEnumValues*/varadTypeBinary=1;varadTypeText=2;/*LineSeparatorEnumValues*/varadLF=10;varadCR=13;varadCRLF=-1;/*StreamWriteEnumValues*/varadWriteChar=0;varadWriteLin…

    2022年10月14日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号