——二叉树

二叉树种类

二叉树有两种主要的形式:满二叉树和完全二叉树。

满二叉树

如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。
在这里插入图片描述

完全二叉树

在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层(h从1开始),则该层包含 1~ 2^(h-1) 个节点。

在这里插入图片描述
堆就是一棵完全二叉树,同时保证父子节点的顺序关系。

二叉搜索树

二叉搜索树是一个有序树。

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 它的左、右子树也分别为二叉排序树

在这里插入图片描述

平衡二叉搜索树

又被称为AVL(Adelson-Velsky and Landis)树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
在这里插入图片描述

二叉树的存储方式

二叉树可以链式存储,也可以顺序存储。
那么链式存储方式就用指针, 顺序存储的方式就是用数组。

链式存储在这里插入图片描述

顺序存储

在这里插入图片描述
如果父节点的数组下标是 i,那么它的左孩子就是 i * 2 + 1,右孩子就是 i * 2 + 2。

二叉树的遍历方式

二叉树主要有两种遍历方式:

  1. 深度优先遍历:先往深走,遇到叶子节点再往回走。
  2. 广度优先遍历:一层一层的去遍历。

前中后,其实指的就是中间节点的遍历顺序
深度优先遍历
前序遍历(递归法,迭代法)
中序遍历(递归法,迭代法)
后序遍历(递归法,迭代法)
在这里插入图片描述

广度优先遍历
层次遍历(迭代法)

作者声明

如有问题,欢迎指正!

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

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

相关文章

buuctf web 前5题

目录 一、[极客大挑战 2019]EasySQL 总结: 二、[极客大挑战 2019]Havefun 总结: 三、[HCTF 2018]WarmUp 总论: 四、[ACTF2020 新生赛]Include 总结: 五、[ACTF2020 新生赛]Exec 总结: 一、[极客大挑战 2019]…

VPS使用环境受限?亚马逊云科技Amazon Lightsail为开发者提供更多选择

对于开发者而言,当你想构建系统架构时,你的面前就出现了两种选择,选择一是花时间去亲手挑选每个亚马逊云科技组件(云服务器、存储、IP地址等),然后自己组装起来;选择二是只需要一个预先配置且预…

C语言经典100例题(51-54)--学习使用按位与 ,按位或 |,按位异或 ^和按位取反~

目录 题目 问题分析 按位与操作符(&) 按位或操作符(|) 按位异或操作符(^) 按位取反操作符(~) 代码及运行结果 题目 学习使用按位与& ,按位或 |,按位异或 ^和按位取反…

解决微信开发者工具企业微信小程序模式下模拟器白屏问题

前一天晚上没有关电脑,第二天发现电脑自己重启了,然后微信开发者工具就出了问题,在企业微信小程序模式下,模拟器出现了白屏,只有上方title可以正常显示。点击模拟器右上角三个点都不出弹出菜单,并且在调试器…

初识Nacos

前言 Nacos是一个用于微服务架构下的服务发现和配置管理以及服务管理的综合解决方案(官网介绍),这里的服务发现其实就是注册中心,配置管理就是配置中心,而服务管理是二者的综合; Nacos特性 1.服务发现与…

李宏毅机器学习笔记:RNN循环神经网络

RNN 一、RNN1、场景引入2、如何将一个单词表示成一个向量3种典型的RNN网络结构 二、LSTMLSTM和普通NN、RNN区别 三、 RNN的训练RNN与auto encoder和decoder 四、RNN和结构学习的区别五、pytorch实现RNN与LSTM5.1为何 H o u t h i d d e n s i z e H_{out}hidden_size Hout​hi…

一个集成的BurpSuite漏洞探测插件1.1

免责声明 本文发布的工具和脚本,仅用作测试和学习研究,禁止用于商业用途,不能保证其合法性,准确性,完整性和有效性,请根据情况自行判断。如果任何单位或个人认为该项目的脚本可能涉嫌侵犯其权利&#xff0c…

Mysql数据库基础总结:

什么是数据库: 数据库(DataBase):存储和管理数据的一个仓库。 数据库类型分为:关系型数据库和非关系型数据库。 关系型数据库(SQL):存储的数据以行和列为格式,类似于e…

手写Mybatis

Mybatis核心配置文件就是为了配置Configration 因此要首先会解析Mybatis核心配置文件 首先使用dom4J解析Mybatis核心配置文件 新建模块演示dom4j解析.xml 目录放错了 无所谓 引入依赖 从原来项目可以拷贝过来 就些简单配置就好 解析核心配置文件和解析xxxMapper.xml映射文件…

vue学习之属性绑定

内容渲染 采用 &#xff1a;进行属性渲染创建 demo3.html,内容如下 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"&…

CHS零壹视频恢复程序OCR使用方法

目前CHS零壹视频恢复程序监控版、专业版、高级版已经支持了OCR&#xff0c;OCR是一种光学识别系统&#xff0c;通俗说就和扫描仪带的OCR软件一样的原理&#xff1a; 分析照片->OCR获取字符串->整理字符串->输出 使用方法如下&#xff08;以CHS零壹视频恢复程序监控版…

使用LlamaIndex构建自己的PandasAI

推荐&#xff1a;使用 NSDT场景编辑器 快速搭建3D应用场景 Pandas AI 是一个 Python 库&#xff0c;它利用生成 AI 的强大功能来增强流行的数据分析库 Pandas。只需一个简单的提示&#xff0c;Pandas AI 就可以让你执行复杂的数据清理、分析和可视化&#xff0c;而这以前需要很…

STL线程各种容器对比、数组和vector如何互相转换

STL vector如何扩展内存和释放内存STL中各种容器对比STL中的swap函数STL中哈希表扩容STL迭代器失效的情况和原因vector删除元素后如何避免当前迭代器会失效vector的iterator和const_iterator和const iterator vector如何扩展内存和释放内存 内存增长 1.5还是2倍扩容 gcc 二倍扩…

微信小程序ibeacon搜索功能制作

以下是一个完整的微信小程序代码示例&#xff0c;演示如何实现iBeacon搜索功能&#xff1a; // 在小程序页面中的js文件中编写代码Page({data: {beacons: [] // 存储搜索到的iBeacon设备信息},onReady() {// 初始化iBeaconwx.startBeaconDiscovery({uuids: [你的UUID], // 替换…

数据结构和算法(1):开始

算法概述 所谓算法&#xff0c;即特定计算模型下&#xff0c;旨在解决特定问题的指令序列 输入 待处理的信息&#xff08;问题&#xff09; 输出 经处理的信息&#xff08;答案&#xff09; 正确性 的确可以解决指定的问题 确定性 任一算法都可以描述为一个由基本操作组成的序…

用户促活留存新方式——在APP中嵌入小游戏

随着APP同类产品的不断出现&#xff0c;APP开发者们面临着激烈的竞争&#xff0c;很多APP下载后被新的APP取代&#xff0c;获客成本越来越高。同时开发者还会面临用户粘性差、忠诚度低、用完即走、留存困难&#xff0c;商业化价值被大大缩减。 在APP中植入小游戏来提高用户活跃…

Vue——vue3+element plus实现多选表格使用ajax发送id数组

代码来源: Vue 3结合element plus&#xff08;问题总结二&#xff09;之 table组件实现多选和清除选中&#xff08;在vue3中获取ref 的Dom&#xff09;_multipletableref.value.togglerowselection()打印出来的是u_子时不睡的博客-CSDN博客 前言 为了实现批量删除功能的功能…

【Python爬虫实战】爬虫封你ip就不会了?ip代理池安排上

前言 在进行网络爬取时&#xff0c;使用代理是经常遇到的问题。由于某些网站的限制&#xff0c;我们可能会被封禁或者频繁访问时会遇到访问速度变慢等问题。因此&#xff0c;我们需要使用代理池来避免这些问题。本文将为大家介绍如何使用IP代理池进行爬虫&#xff0c;并带有代…

C语言练习:输入日期输出该日期为当年第几天

用scanf()输入某年某月某日&#xff0c;判断这一天是这一年的第几天。以3月5日为例&#xff0c;应该先把前两个月的加起来&#xff0c;然后再加上5天即本年的第几天&#xff0c;特殊情况&#xff0c;闰年且输入月份≥3时需考虑多加一天。注&#xff1a;判断年份是否为闰年的方法…

【C刷题】day1

一、选择题 1.正确的输出结果是 int x5,y7; void swap() { int z; zx; xy; yz; } int main() { int x3,y8; swap(); printf("%d,%d\n"&#xff0c;x, y); return 0; } 【答案】&#xff1a; 3&#xff0c;8 【解析】&#xff1a; 考点&#xff1a; &#xff…