算法笔记:二叉树

这篇具有很好参考价值的文章主要介绍了算法笔记:二叉树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1 基本二叉树

  • 二叉树是一种树形数据结构,其中每个节点最多有两个子节点,通常称为“左子节点”和“右子节点”。
    • 二叉树的根是唯一没有父节点的节点,而所有其他节点都有一个父节点和零个或两个子节点。

1.1 基础术语

  • 节点(Node): 二叉树的基本单位。每个节点都有一个关键字(或称为“键值”或“数据”)。
  • 根节点(Root Node): 没有父节点的节点。
  • 叶节点(Leaf Node): 没有子节点的节点。
  • 子树(Subtree): 任何节点都可以视为其下的所有节点组成的一个新树。
  • 深度(Depth): 从根节点到某一节点的简单路径上的边数。
  • d层(Level): 树中所有深度为d的节点的集合。

算法笔记:二叉树,算法,算法,笔记,数据结构

1.2 二叉树的遍历

以如下二叉树为例

算法笔记:二叉树,算法,算法,笔记,数据结构

1.2.1 前序遍历

 先访问根节点,然后访问左子树,再访问右子树

算法笔记:二叉树,算法,算法,笔记,数据结构

ABDHIEJCFKG

1.2.1.1 非递归实现

算法笔记:二叉树,算法,算法,笔记,数据结构

算法笔记:二叉树,算法,算法,笔记,数据结构

1.2.2 中序遍历 

先访问左子树,再访问根节点,最后访问右子树

HDIBEJAFKCG

算法笔记:二叉树,算法,算法,笔记,数据结构

1.2.2.1 非递归实现

算法笔记:二叉树,算法,算法,笔记,数据结构

算法笔记:二叉树,算法,算法,笔记,数据结构

1.2.3 后序排列

 先访问左子树,再访问右子树,最后访问根节点

HIDJEBKFGCA

算法笔记:二叉树,算法,算法,笔记,数据结构

1.2.3.1 非递归实现

算法笔记:二叉树,算法,算法,笔记,数据结构
算法笔记:二叉树,算法,算法,笔记,数据结构

算法笔记:二叉树,算法,算法,笔记,数据结构

注:下面我实现了一种两步进栈法,不知道是对的还是不对的(输出的结果是一样的)

算法笔记:二叉树,算法,算法,笔记,数据结构

1.2.4 层次遍历

逐层的从根节点开始,每层从左至右遍历

ABCDEFGHIJK

算法笔记:二叉树,算法,算法,笔记,数据结构

1.2.5 前序+中序,唯一确定一棵二叉树

算法笔记:二叉树,算法,算法,笔记,数据结构

  • 同理,由二叉树的后序序列和中序序列同样可以唯一地确定一棵二叉树
  • 但是,已知二叉树的前序遍历序列和后序遍历序列却无法确定一棵二叉树
    • 比如:已知一棵二叉树的前序遍历序列为A、B,后序遍历序列为B、A
    • 我们虽然可以很容易地得知结点A为根结点,但是无法确定结点B是结点A的左儿子还是右儿子,因为B无论是结点A的右儿子还是左儿子都是符合已知条件的。

1.3 二叉树的性质

1.3.1 每一层最多多少个节点

一棵非空二叉树的第 i 层上最多有个结点(i≥1)

算法笔记:二叉树,算法,算法,笔记,数据结构

1.3.2 每一棵树最多多少个节点

一棵高度为k的二叉树,最多具有个结点

算法笔记:二叉树,算法,算法,笔记,数据结构

1.3.3 叶子节点数量和度数为2的节点数量

对于一棵非空二叉树,如果叶子结点数为n0,度数为2的结点数为n2,则有:  n0=n2+1 成立。

算法笔记:二叉树,算法,算法,笔记,数据结构

算法笔记:二叉树,算法,算法,笔记,数据结构

1.3.4 具有n个节点的完全二叉树的高度

算法笔记:二叉树,算法,算法,笔记,数据结构

1.4 二叉树的实现

1.4.1 顺序存储

1.4.1.1 完全二叉树的顺序存储

算法笔记:二叉树,算法,算法,笔记,数据结构

1.4.1.2 普通二叉树的顺序存储

算法笔记:二叉树,算法,算法,笔记,数据结构

算法笔记:二叉树,算法,算法,笔记,数据结构

1.4.1.3 顺序存储的特点

  • 存储空间的浪费。
  • 一般只用于一些特殊的场合,如静态的、并且结点个数已知的完全二叉树或接近完全二叉树的二叉树。

1.4.2 链式存储

算法笔记:二叉树,算法,算法,笔记,数据结构

1.4.2.1 标准形式举例

算法笔记:二叉树,算法,算法,笔记,数据结构

1.4.2.2 广义标准形式举例

算法笔记:二叉树,算法,算法,笔记,数据结构

2 斜二叉树

只有左子节点或只有右子节点的二叉树称为斜二叉树

算法笔记:二叉树,算法,算法,笔记,数据结构

3 满二叉树

所有的分支要么左右子节点都有,要么没有子节点,且所有叶子结点都在同一层上

算法笔记:二叉树,算法,算法,笔记,数据结构

4 完全二叉树

除了最后一层外,每一层都是完全填满的,并且所有节点都尽量向左填充

另一种说法:在满二叉树的最底层自右至左依次(注意:不能跳过任何一个结点)去掉若干个结点得到的二叉树

算法笔记:二叉树,算法,算法,笔记,数据结构

完全二叉树特点:

  • 叶子结点只能出现在最下两层;
  • 最下层的叶子结点一定集中在左边并且连续;
  • 若结点度为1,则该节点只有左子节点;
  • 完全二叉树的深度为算法笔记:二叉树,算法,算法,笔记,数据结构 (n是树中节点的数量)
  • 在高度为h的完全二叉树中,节点数最少为,最多为
  • 对于个索引为i的点(索引从1开始计数)
    • 父节点(若存在)的索引是
    • 左子节点(若存在)的索引是2i
    • 右子节点(若存在)的索引是2i+1
  • 对任一结点,如果其右子树的高度为k,则其左子树的高度为k或k+1

满二叉树一定是完全二叉树,而完全二叉树不一定是满二叉树

5 线索二叉树

  • 线索二叉树是一种对二叉树的改进,旨在通过线索(也就是额外的指针)加速对树的遍历操
  • 在普通的二叉树中,每个节点有两个子节点:左子节点和右子节点。但有些节点的子节点可能为空,这些空指针字段不存储任何信息
    • 算法笔记:二叉树,算法,算法,笔记,数据结构
  • 线索二叉树通过利用这些空指针字段来存储与当前节点在某种遍历顺序(如前序、中序或后序)下相邻的节点。
    • 这样,在遍历树时,就不需要使用栈或递归,从而提高了遍历的速度
  • 在线索二叉树中,每个节点有两个额外的标志位,分别表示左指针和右指针是否被用作线索
    • 如果左子节点为空,则左指针字段存储该节点在某种遍历顺序下的前驱节点
    • 如果右子节点为空,则右指针字段存储该节点在某种遍历顺序下的后继节点
  • 算法笔记:二叉树,算法,算法,笔记,数据结构

5.1 创建线索二叉树

创建线索二叉树通常需要两次遍历

  1. 第一次遍历是普通的前序、中序或后序遍历,用于建立二叉树的基本结构。
  2. 第二次遍历用于添加线索。这通常通过保存前一个访问的节点并在访问下一个节点时更新其线索来完成。

5.2 优缺点

优点

  • 遍历更快:由于已经存储了前驱和后继信息,遍历操作更加高效。
  • 不需要额外的数据结构:不需要使用栈或递归。

缺点

  • 额外的存储开销:需要额外的字段来存储线索和标志位。
  • 修改复杂:插入或删除节点时,需要更新相应的线索,这使得操作更加复杂。、

参考内容:数据结构与算法(八)-二叉树(斜二叉树、满二叉树、完全二叉树、线索二叉树)-腾讯云开发者社区-腾讯云 (tencent.com)OO文章来源地址https://www.toymoban.com/news/detail-693877.html

到了这里,关于算法笔记:二叉树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二叉树(上)——“数据结构与算法”

    各位CSDN的uu们好呀,好久没有更新我的数据结构与算法专栏啦,今天,小雅兰继续来更新二叉树的内容,下面,让我们进入链式二叉树的世界吧!!! 二叉树链式结构的实现  二叉树链式结构的实现 普通的二叉树的增删查改是没有价值的!!! 只有搜索二叉树的增删查改才

    2024年02月15日
    浏览(45)
  • 【数据结构】树与二叉树(十三):递归复制二叉树(算法CopyTree)

      二叉树是一种常见的树状数据结构,它由结点的有限集合组成。一个二叉树要么是 空集 ,被称为 空二叉树 ,要么由一个根结点和两棵不相交的子树组成,分别称为 左子树 和 右子树 。每个结点最多有两个子结点,分别称为左子结点和右子结点。 引理5.1:二叉树中层数

    2024年02月01日
    浏览(40)
  • 【数据结构与算法】树与二叉树

    除了之前我们讲的栈、队列、链表等线性结构,数据结构中还有着一对多的 非线性结构 ——— 树 。 树是有 n 个结点组成的有限集,当n=0时为空树,在任意一颗非空树中,有且仅有一个 特定的根结点 ;当n1时,其余结点又可以分为一棵树,称为根的 子树 。 如下图所示: A为

    2023年04月09日
    浏览(50)
  • 数据结构与算法——树与二叉树

    😊各位小伙伴久等了,本专栏新文章出炉了!!! 我又回来啦,接下来的时间里,我会持续把数据结构与算法专栏更新完。 👉树型结构👈 是一类重要的 ✍非线性数据结构 ,其中以树和二叉树最为常用,直观来看,树是以分支关系定义的层次结构。树型结构在客观世界中

    2024年02月11日
    浏览(46)
  • 数据结构与算法之《二叉树》详解

    文章目录 一、树的概念及结构 二、二叉树的概念及结构 2、1 二叉树的概念 2、2 二叉树的特点 2、3 二叉树的结构(图片) 2、4 特殊的二叉树 三、二叉树的代码及思路实现 3、1 二叉树的存储结构 3、1、1 二叉树的顺序存储结构 3、1、2 二叉树的链式存储结构 3、2 二叉树链式

    2024年02月01日
    浏览(45)
  • 【数据结构和算法】---二叉树(1)--树概念及结构

    树是一种 非线性的数据结构 ,它是由n(n=0)个有限结点组成一个具有层次关系的集合。之所以叫它树,是因为将此结构倒转后与现实生活中的树极其相似,一个主干分出多个分支,分支还可继续分展。 有一个特殊的结点,称为 根结点 ,根节点没有前驱结点; 除根节点外,

    2024年02月03日
    浏览(43)
  • 【数据结构】二叉树算法讲解(定义+算法原理+源码)

    博主介绍:✌全网粉丝喜爱+、前后端领域优质创作者、本质互联网精神、坚持优质作品共享、掘金/腾讯云/阿里云等平台优质作者、擅长前后端项目开发和毕业项目实战✌有需要可以联系作者我哦! 🍅附上相关C语言版源码讲解🍅 👇🏻 精彩专栏推荐订阅👇🏻 不然下次找

    2024年01月23日
    浏览(54)
  • 《数据结构与算法》之二叉树(补充树)

    二叉搜索树,也称二叉排序树或二叉查找树 二叉搜索树:一棵二叉树,可以为空,如果不为空,应该满足以下性质: 非空左子树的所有结点小于其根结点的键值 非空右子树的所有结点大于其根结点的键值 左右子树都是二叉搜索树 对于二叉树的查找,其实沿用的是分治法的

    2024年02月08日
    浏览(49)
  • 【数据结构与算法】力扣:对称二叉树

    给你一个二叉树的根节点 root , 检查它是否轴对称。 示例 1: 输入:root = [1,2,2,3,4,4,3] 输出:true 示例 2: 输入:root = [1,2,2,null,3,null,3] 输出:false 来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/symmetric-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请

    2024年02月13日
    浏览(38)
  • 算法与数据结构(五)--二叉树入门

    符号表的增删查操作,随着元素个数N的增多,其耗时也是线性增多的,时间复杂度都是O(n),为了提高运算效率,我们学习树这种数据结构。 目录 一.树的基本定义 二.树的相关术语 三.二叉树的基本定义 四.二叉树的链表实现 1.二叉树结点类 结点类API设计:​编辑 代码实现:

    2024年02月12日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包