算法笔记:二叉树

1 基本二叉树

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

1.1 基础术语

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

1.2 二叉树的遍历

以如下二叉树为例

1.2.1 前序遍历

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

ABDHIEJCFKG

1.2.2 中序遍历 

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

HDIBEJAFKCG

1.2.3 后序排列

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

HIDJEBKFGCA

1.2.4 层次遍历

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

ABCDEFGHIJK

2 斜二叉树

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

3 满二叉树

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

4 完全二叉树

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

完全二叉树特点:

  • 叶子结点只能出现在最下两层;
  • 最下层的叶子结点一定集中在左边并且连续;
  • 若结点度为1,则该节点只有左子节点;
  • 完全二叉树的深度为\left \lceil \log_2(n+1) \right \rceil (n是树中节点的数量)
  • 在高度为h的完全二叉树中,节点数最少为2^{h-1},最多为2^h-1
  • 对于个索引为i的点(索引从1开始计数)
    • 父节点(若存在)的索引是\left \lfloor i/2 \right \rfloor
    • 左子节点(若存在)的索引是2i
    • 右子节点(若存在)的索引是2i+1

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

5 线索二叉树

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

5.1 创建线索二叉树

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

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

5.2 优缺点

优点

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

缺点

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

参考内容:数据结构与算法(八)-二叉树(斜二叉树、满二叉树、完全二叉树、线索二叉树)-腾讯云开发者社区-腾讯云 (tencent.com)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/120008.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ApiPost7使用介绍 | HTTP Websocket

一、基本介绍 创建项目(团队下面可以创建多个项目节点,每个项目可以创建多个接口): 参数描述库(填写参数时自动填充描述): 新建环境(前置URL、环境变量很有用)&#x…

【GitLab私有仓库】在Linux上用Gitlab搭建自己的私有库并配置cpolar内网穿透

文章目录 前言1. 下载Gitlab2. 安装Gitlab3. 启动Gitlab4. 安装cpolar5. 创建隧道配置访问地址6. 固定GitLab访问地址6.1 保留二级子域名6.2 配置二级子域名 7. 测试访问二级子域名 前言 GitLab 是一个用于仓库管理系统的开源项目,使用Git作为代码管理工具&#xf…

【搭建私人图床】使用LightPicture开源搭建图片管理系统并远程访问

文章目录 1.前言2. Lightpicture网站搭建2.1. Lightpicture下载和安装2.2. Lightpicture网页测试2.3.cpolar的安装和注册 3.本地网页发布3.1.Cpolar云端设置3.2.Cpolar本地设置 4.公网访问测试5.结语 1.前言 现在的手机越来越先进,功能也越来越多,而手机…

【STM32】学习笔记-SPI通信

SPI通信 SPI通信(Serial Peripheral Interface)是一种同步的串行通信协议,用于在微控制器、传感器、存储器、数字信号处理器等之间进行通信。SPI通信协议需要使用4个线路进行通信:时钟线(SCLK)、主输入/主输出线(MISO)、主输出/主…

算法leetcode|76. 最小覆盖子串(rust重拳出击)

文章目录 76. 最小覆盖子串:样例 1:样例 2:样例 3:提示:进阶: 分析:在这里插入图片描述 题解:rust:go:c:python:java: 76.…

马斯克谈 Facebook 不开源算法

导读虽然马斯克与扎克伯格的 “八角笼中” 之约没有达成,但很显然,马斯克并不打算就此罢休。既然没能在线下大战一场,那自然不会错过在线上 “出招” 的机会。 他转发了一则推文,并说道:“在地球上,Facebo…

【【萌新的STM32学习25--- USART寄存器的介绍】】

萌新的STM32学习25- USART寄存器的介绍 STM32–USART寄存器介绍(F1) 控制寄存器1 (CR1) 位13: 使能USART UE 0: USART分频器和输出被禁止 1: USART模块使能 位12 : 配置8个数据位…

chrono学习(一)

我想用chrono进行沙土的仿真,首先学习demo_GPU_ballCosim.cpp,这个例子仿真了一些沙土的沉降过程。 首先,运行编辑完成的文件demo_GPU_ballCosim: (base) eowyneowyn-MS-7D20:~/build_chrono/bin$ ./demo_GPU_ballCosim 运行完得…

mac常见问题(三) macbook键盘溅上水怎么办?

多朋友在使用mac的时候难免会发生一些小意外,例如说本期要为大家说的macbook键盘溅上水或者其他的液体怎么办?不清楚的同学赶快get这项技能吧! 如果你不小心给你的MacBook键盘上溅了水或者其他液体,你需要超级快的把表面的液体清理…

【Java】关于JDK 8的HashMap

文章目录 HashMap 简介数据结构Hash构造方法get(key)方法步骤一:通过key获取所在桶的第一个元素是否存在步骤二:该节点的hash和key是否与要查询的hash和key匹配步骤三:当对应桶中不止一个节点时,根据不同节点类型查询 put(key,value)为什么树化&#xff…

l8-d6 socket套接字及TCP的实现框架

一、socket套接字 /*创建套接字*/ int socket(int domain, int type, int protocol); /*绑定通信结构体*/ int bind(int sockfd, const struct sockaddr *addr, socklen_t addrlen); /*监听套接字*/ int listen(int sockfd, int backlog); /*处理客户端发起的连接&#xff0…

WorldCoin 运营数据,业务安全分析

WorldCoin 运营数据,业务安全分析 Worldcoin 的白皮书中声明,Worldcoin 旨在构建一个连接全球人类的新型数字经济系统,由 OpenAI 创始人 Sam Altman 于 2020 年发起。通过区块链技术在 Web3 世界中实现更加公平、开放和包容的经济体系&#…

利用python制作AI图片优化工具

将模糊图片4K高清化效果如下: 优化前的图片 优化后如下图: 优化后图片变大变清晰了效果很明显 软件界面如下: 所用工具和代码: 1、所需软件包 网盘链接:https://pan.baidu.com/s/1CMvn4Y7edDTR4COfu4FviA提取码&…

常用的css样式

1:flex布局 .flex-between {display: flex;justify-content: space-between; }.flex-evenly {display: flex;justify-content: space-evenly; }.flex-end {display: flex;justify-content: flex-end; }.flex {display: flex; }.flex-center {display: flex;justify…

失效的访问控制及漏洞复现

失效的访问控制(越权) 1. 失效的访问控制(越权) 1.1 OWASP TOP10 1.1.1 A5:2017-Broken Access Control 未对通过身份验证的用户实施恰当的访问控制。攻击者可以利用这些缺陷访问未经授权的功能或数据,例如:访问其他用户的帐户、查看敏感文件、修改其…

攻防世界-web2

原题 解题思路 miwen应该是密文的拼音。在函数encode中&#xff0c;传入字符串str&#xff0c;依次将str中的每一个字符转换为十进制ASCII码加一&#xff0c;然后再转换成字符。逆向思路构建代码如下&#xff1a; <?php $miwen"a1zLbgQsCESEIqRLwuQAyMwLyq2L5VwBxqGA…

ES6中导入import导出export

ES6使用 export 和 import 来导出、导入模块 用法 /** 导出 export *///分别导出 export let name 孙悟空; export function sum(a, b) {return a b; } } //先定义再导出 let age 18 export {age}/** 默认导出 export default */const a 默认导出; export default a;/**…

汇编--int指令

中断信息可以来自CPU的内部和外部&#xff0c; 当CPU的内部有需要处理的事情发生的时候&#xff0c;将产生需要马上处理的中断信息&#xff0c;引发中断过程。在http://t.csdn.cn/jihpG&#xff0c;我们讲解了中断过程和两种内中断的处理。 这一章中&#xff0c; 我们讲解另一种…

栈和队列OJ

一、括号的匹配 题目介绍&#xff1a; 思路&#xff1a; 如果 c 是左括号&#xff0c;则入栈 push&#xff1b;否则通过哈希表判断括号对应关系&#xff0c;若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c 不对应&#xff0c;则提前返回 false。栈 stack 为空&#xff1…

基于单片机的太阳能热水器控制器设计

一、项目介绍 随着环保意识的逐渐增强&#xff0c;太阳能热水器作为一种清洁能源应用得越来越广泛。然而&#xff0c;传统的太阳能热水器控制器通常采用机械式或电子式温控器&#xff0c;存在精度低、控制不稳定等问题。为了解决这些问题&#xff0c;本项目基于单片机技术设计…