二叉树基础知识总结

目录

二叉树基础知识

概念 : 

根节点的五个形态 : 

特殊的二叉树

满二叉树 : 

 完全二叉树 : 

二叉搜索树  :

平衡二叉搜索树 : 

二叉树的性质 : 

二叉树的存储结构

二叉树的顺序存储结构

二叉树的链式存储结构

 二叉树的遍历方式 : 

基础概念

前中后遍历

 层序遍历 : 


二叉树基础知识

概念 : 

二叉树(binary tree)是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树。

根节点的五个形态 : 

  1. 空二叉树

  2. 只有一个根结点

  3. 根结点只有左子树

  4. 根结点只有右子树

  5. 根结点既有左子树又有右子树

特殊的二叉树

满二叉树 : 

概念 : 

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

图例 : 

 完全二叉树 : 

概念 : 

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

图例 : 

 而

 这个就不是一颗完全二叉树!

二叉搜索树  :

前面介绍的树,都没有数值的,而二叉搜索树是有数值的了,二叉搜索树是一个有序树

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

下面的就是一颗二叉搜索树;

 二叉搜索树最大的特点就是左<父<右 ;

平衡二叉搜索树 : 

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

其中c++中的map、set、multimap,multiset的底层实现都是平衡二叉搜索树,所以map、set的增删操作时间时间复杂度是logn , 而unordered_map、unordered_set,unordered_map、unordered_set底层实现是哈希表。

二叉树的性质 : 

  1. 二叉树的第i层上至多有2 ^ (i-1)(i≥1)个节点。

  2. 深度为h的二叉树中至多含有2^h-1个节点

  3. 若在任意一棵二叉树中,有 n0 个叶子节点,有 n2 个度为2的节点,则必有n0 = n2 + 1

  4. 具有n个节点的完全二叉树深为log2(x) + 1(其中x表示不大于n的最大整数)

  5. 若对一棵有n个节点的完全二叉树进行顺序编号(1<=i<=n),那么,对于编号为i(i>=1)的节点:

    ⑴i =1 时,该节点为根,它无双亲节点 。

    ⑵ i > 1 时,该节点的双亲节点的编号为i/2 。

    ⑶2i<= n,则有编号为2i的左节点,否则没有左节点 。

    ⑷2i+1<=n ,则有编号为2i+1的右节点,否则没有右节点 。

二叉树的存储结构

二叉树可以顺序存储,也可以链式存储 ;

二叉树的顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点,并且结点的存储位置,也就是数组的下标要能体现结点之间的逻辑关系,比如双亲与孩子的关系,左右兄弟的关系等。

如以下这颗完全二叉树 : 

 可以采用以下线性表来存储:

下标12345678910
数据ABCDEFGHIJ

 如果父节点的数组下标是 i,那么它的左孩子就是 i * 2 + 1,右孩子就是 i * 2 + 2。

二叉树的链式存储结构

在链式结构中,一个二叉树的结点包含左孩子指针,数据,右孩子指针 ;

链式存储效果如图 : 

二叉链表的结构体定义 : 


typedef struct BiTNode
{TElemType data;  //数据域struct BiTNode *lchild,*rchild; //指针域
}BiTNode,*BiTree;

 二叉树的遍历方式 : 

基础概念

首先,主要的两种遍历方式为 : 

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

这两种遍历方法又可以细分 : 

  • 深度优先遍历
    • 前序遍历(递归法,迭代法)
    • 中序遍历(递归法,迭代法)
    • 后序遍历(递归法,迭代法)
  • 广度优先遍历
    • 层次遍历(迭代法)

前中后遍历

其中前中后三种结点的遍历顺序 如下 :

  • 前序遍历:中左右
  • 中序遍历:左中右
  • 后序遍历:左右中

图例 : 

 层序遍历 : 

从树的第一层开始访问,从上而下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问 ;

如下图 : 

 层序遍历的结果为 : 

ABCDEFGHI 

参考 : 

  1. 《大话数据结构》

  2. 《数据结构》C语言版(清华严蔚敏考研版)

  3. 【数据结构与算法】二叉树

  4. 代码随想录

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

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

相关文章

新年新策略:2024数字化转型宝典,锁定趋势预测与关键部署策略

官.网地址&#xff1a;合合TextIn - 合合信息旗下OCR云服务产品 2024年是实现“十四五”规划目标任务的关键一年&#xff0c;以数字化驱动生产方式、生活方式和治理方式全面变革依旧是重中之重而作为数字化转型的助推器&#xff0c;信创同样是实现相关规划目标的一大抓手&…

OpenAI Sora引领AI跳舞视频新浪潮:字节跳动发布创新舞蹈视频生成框架

OpenAI的Sora已经引起广泛关注&#xff0c;预计今年AI跳舞视频将在抖音平台上大放异彩。下面将为您详细介绍一款字节跳动发布的AI视频动画框架。 技术定位&#xff1a;这款框架采用先进的diffusion技术&#xff0c;专注于生成人类舞蹈视频。它不仅能够实现人体动作和表情的迁移…

从零开始学习Netty - 学习笔记 - NIO基础 - 网络编程: Selector

4.网络编程 4.1.非阻塞 VS 阻塞 在网络编程中&#xff0c;**阻塞&#xff08;Blocking&#xff09;和非阻塞&#xff08;Non-blocking&#xff09;**是两种不同的编程模型&#xff0c;描述了程序在进行网络通信时的行为方式。 阻塞&#xff08;Blocking&#xff09;&#xff1…

电商平台商家结算

本文主要分析了目前电商清结算的流程以及自己对电商清结算的看法。 基本概念 先说下电商平台清结算的概念。简单说就是收的用户&#xff08;C端&#xff09;的付款&#xff0c;经过清分&#xff0c;再结算给对应商家。当然&#xff0c;这里排除那种资金不通过第三方&#xff0c…

django自定义后端过滤

​ DRF自带的过滤 第一个 DjangoFilterBackend 是需要安装三方库见[搜索&#xff1a;多字段筛选]两外两个是安装注册了rest_framework就有。 如上图&#xff0c;只要配置了三个箭头所指的方向&#xff0c;就能使用。 第一个单字段过滤 用户视图集中加上filterset_fields …

linux 系统的目录结构

为什么某些执行程序位于/bin、/sbin、/usr/bin或/usr/sbin目录下&#xff1f;例如&#xff0c;less命令位于/usr/bin目录下。为什么不是/bin、/sbin或/usr/sbin&#xff1f;这些目录之间有什么区别呢&#xff1f; 在这篇文章中&#xff0c;让我们主要讲述一下Linux文件系统结构…

IP协议及相关技术协议

一、IP基本认识 1. IP的作用 IP在TCP/IP模型中处于网络层&#xff0c;网络层的主要作用是实现主机与主机之间的通信&#xff0c;而IP的作用是在复杂的网络环境中将数据包发送给最终目的主机。 2. IP与MAC的关系 简单而言&#xff0c;MAC的作用是实现“直连”的两个设备之通信…

【深入理解设计模式】 工厂设计模式

工厂设计模式 工厂设计模式是一种创建型设计模式&#xff0c;它提供了一种在不指定具体类的情况下创建对象的接口。在工厂设计模式中&#xff0c;我们定义一个创建对象的接口&#xff0c;让子类决定实例化哪一个类。工厂方法使一个类的实例化延迟到其子类。 工厂设计模式的目…

Web安全之浅见

备注&#xff1a;这是我在2017年在自己的网站上写的文章&#xff0c;今天迁移过来。 昨天去参加了公司组织的一个关于网络安全的培训&#xff0c;了解了很多关于网络安全方面的知识&#xff0c;也才意识到网络安全是一项极其重要的领域。 本篇文章主要聊聊Web安全。不过我对于网…

区块链游戏解说:什么是 Planet IX

作者&#xff1a;lesleyfootprint.network 编译&#xff1a;cicifootprint.network 数据源&#xff1a;Planet IX Dashboard 什么是 Planet IX Planet IX&#xff0c;一个由原生 IX TOKEN 推动的 Web3 玩赚平台。作为一款 GameFi 策略游戏&#xff0c; Planet IX 上的每项资…

ArcgisForJS如何访问Arcgis Server?

文章目录 0.引言1.准备ArcGIS相关工具2.创建含有ArcSDE地理数据库的MXD文件3.注册ArcSDE地理数据库4.发布数据到Arcgis Server5.ArcgisForJS访问ArcGIS Server数据 0.引言 ArcGIS API for JavaScript 是一个用于在Web和移动应用程序中创建交互式地图和地理空间分析应用的库。它…

Prometheus+TDengine集群实现监控体系高可用

背景 为避免再次出现因Prometheus宕机导致业务无法查看历史数据受到影响&#xff0c;准备将Prometheus架构从单节点方式升级为高可用集群方式并将后端存储由本地存储改为远端分布式时序数据库存储。分布式时序数据库采用国产数据库TDengine。 架构 解释&#xff1a;虚线代表P…

【服务器】服务器推荐

一、引言 在数字世界的浪潮中&#xff0c;服务器作为数据存储和处理的基石&#xff0c;其重要性不言而喻。而在这个繁星点点的市场中&#xff0c;雨云以其独特的优势和超高的性价比&#xff0c;逐渐成为众多企业和个人的首选。今天&#xff0c;就让我带你走进雨云的世界&#…

排序前言冒泡排序

目录 排序应用 常见的排序算法 BubbleSort冒泡排序 整体思路 图解分析 ​ 代码实现 每趟 写法1 写法2 代码NO1 代码NO2优化 时间复杂度 排序概念 排序&#xff1a;所谓排序&#xff0c;就是使一串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递…

QY-800S土壤水分测量仪的使用场景和功能作用

技术参数 ◆土壤湿度 测量范围&#xff1a;干土&#xff5e;饱和土 测量精度&#xff1a;3% 分辨率&#xff1a;0.1% ◆土壤温度 测量范围&#xff1a;-30℃&#xff5e;70℃ 测量精度&#xff1a;0.3℃ 分辨率&#xff1a;0.1℃ ◆记录间隔&#xff1a;30 分&#xff5…

数据分析(二)自动生成分析报告

1. 报告生成思路概述 怎么快速一份简单的数据分析报告&#xff0c;注意这个报告的特点&#xff1a; --网页版&#xff0c;可以支持在线观看或者分享HTML文件 --标题&#xff0c;动图&#xff0c;原始数据应有尽有 --支持交互&#xff0c;比如plotly交互画面&#xff0c;数据…

数论之约数(试除法求约数,约数个数,约数和)算法原理讲解及其实现

约数问题&#xff1a; 试除法&#xff1a; d|n 那么 n/d|n 也是成立的-----> 成对出现的 d<n/d d小于等于根号n 举例&#xff1a; 假如2是12的约数&#xff0c;那么6也是12的约数。 #include <iostream> #include <algorithm> #include <vector> #…

交换瓶子【第七届】【省赛】【A组】

题目描述 有N个瓶子&#xff0c;编号 1 ~ N&#xff0c;放在架子上。 比如有5个瓶子&#xff1a; 2 1 3 5 4 要求每次拿起2个瓶子&#xff0c;交换它们的位置。 经过若干次后&#xff0c;使得瓶子的序号为&#xff1a; 1 2 3 4 5 对于这么简单的情况&#xff0c;显然&#…

IDEA-常用插件

1、Mybatis Log Free 当我们使用mybatis log在控制台输出sql 内容&#xff0c;输出内容将语句与参数分开打印&#xff0c;还需要手动将参数替换到指定位置。 使用对应插件后&#xff0c;自动将输出内容组装成完整的可直接执行的SQL 在插件市场 查看对应名称&#xff0c;并安装。…

Android进阶(二十九) 走近 IntentFilter

文章目录 一、什么是IntentFilter &#xff1f;二、IntentFilter 如何过滤隐式意图&#xff1f;2.1 动作测试2.2 类别测试2.3 数据测试 一、什么是IntentFilter &#xff1f; 如果一个 Intent 请求在一片数据上执行一个动作&#xff0c; Android 如何知道哪个应用程序&#xf…