【落羽的落羽 数据结构篇】树、二叉树

embedded/2025/2/27 4:11:28/

在这里插入图片描述

文章目录

  • 一、树
    • 1. 树的概念和结构
    • 2. 树的相关术语
  • 二、二叉树
    • 1. 概念与结构
    • 2. 满二叉树
    • 3. 完全二叉树
    • 4. 二叉树的性质
    • 5. 二叉树的存储结构

一、树

1. 树的概念和结构

之前我们学习了线性表,今天我们再来接触一种全新的数据结构——树。
树是一种非线性数据结构,它是有有限个结点组成的一个具有层次关系的结构。把它称为树是因为它看起来就像一棵倒挂的树,根朝上而叶朝下。

现实中的树:
现实中的树

树形结构:
在这里插入图片描述
关于数据结构树:

  • 它有一个根结点,根结点没有前驱结点,如上图的A就是这棵树的根结点。
  • 除根结点外,其余结点被分为有限个互不相交的集合,每一个集合都是一棵子树,每棵子树有且只有一个前驱结点,可以没有后继或多个后继结点。因此,树是递归定义的。
  • 子树不能有交集,否则就不是树形结构。
  • 一棵有n个结点的树有n - 1条边

2. 树的相关术语

  • 父结点/双亲结点:若一个结点有子结点,则这个结点是其子节点的父结点。如上图,A是B、C、D、E的父结点,C是H的父结点。

  • 子结点/孩子结点:若一个结点含有子树,则子树的根结点称为该结点的子结点。如上图,B、C、D、E是A的子结点,K是F的子结点。

  • 结点的度:一个结点有几个孩子,它的度就是多少。如上图,A的度是4,C的度是2,M的度是0。

  • 树的度:一棵树中,所有结点的度中的最大值就是这棵树的度。如上图,这棵树的度是6。

  • 叶子结点/叶节点/终端节点:度为0的结点。如上图,K、G、L、M、N、D、I、O都是叶子结点。

  • 分支结点/非终端结点:度不为0的结点。如上图,A、B、C、E、F、H、J都是分支结点。

  • 兄弟结点:具有相同父结点的结点互称为兄弟结点。如上图,B、C、D、E互称为兄弟结点,I、J互称为兄弟结点。

  • 结点的层次:从根结点开始定义,根结点在第1层,根结点的子结点在第2层,以此类推。如上图,D在第2层、N在第4层。

  • 树的高度/深度:树中结点的最大层次。如上图,这棵树的高度为4。

  • 路径:从一个结点到另一个结点的结序列,结点之间只能通过父子关系连接、如上图,A到L的路径为A-C-H-L,G到O的路径为G-C-A-E-J-O。

  • 结点的子孙:以一个结点为根结点的子树中的所有结点都称为该结点的子孙。如上图,除A外所有结点都是A的子孙,I、J、O都是E的子孙。

  • 结点的祖先:从根结点到一个结点所经分支上的所有结点称之为该节点的祖先。如上图,A是除自己外所有结点的祖先,A、B、F都是K的祖先。

  • 森林:若干棵互不相交的树的集合称为森林。

在这里插入图片描述

二、二叉树

1. 概念与结构

在树形结构中,我们最常用的就是二叉树。二叉树由根结点、左子树、右子树组成,或者为空。
二叉树的特点是:

  • 二叉树的度一定不大于2,也就是二叉树的每一个结点的子结点不多于2个。
  • 二叉树的子树有左右之分,次序不能颠倒。
    在这里插入图片描述

2. 满二叉树

满二叉树是二叉树的特殊情形。一个二叉树如果每一层的结点数都达到最大值,它就是满二叉树。也就是除叶子结点外每一个结点都有两个子结点。不难计算,如果一个满二叉树的高度为k,则它的结点总数是2k -1(等比数列求和)

在这里插入图片描述

3. 完全二叉树

完全二叉树是由满二叉树引出来的。
我们首先要知道二叉树中结点的编号方式:从上到下,从左到右。从第一层开始从左到右从0开始依次编号,第一层编完第二层从左到右编号……直到所有结点编号完
在这里插入图片描述
对于有n个结点的二叉树,若每一个结点都与深度相同的满二叉树的编号从0到n的结点一一位置对应,这个二叉树就是完全二叉树,满二叉树也是完全二叉树。
也可以理解为:完全二叉树的每一层结点个数达到最大,最后一层不一定达到最大,且结点是从左到右依次排列的。
比如,以下这些都是完全二叉树:在这里插入图片描述

4. 二叉树的性质

  • 非空二叉树的第i层上最多有2i-1个结点
  • 深度为h的二叉树的结点数不多于2h-1
  • 具有n个结点的满二叉树的深度为log2(n+1)

5. 二叉树的存储结构

二叉树既可以用顺序结构存储,也可以用链式结构存储,我们之后都要学习。

在这里插入图片描述

本篇完,感谢阅读


http://www.ppmy.cn/embedded/167440.html

相关文章

Flutter - 基础Widget

Flutter 中万物皆 Widget,基础Widget 同步对应 Android View. 普通文本 Text /*** 控制文本样式统一使用 style:TextStyle, 例:fontSize(字体大小),color(颜色),shadows(阴影)等等* 控制文本布局需单独设置:* textAlign(文不对齐方式)* te…

Hadoop 基础原理

Hadoop 基础原理 基本介绍Hadoop 的必要性Hadoop 核心组件Hadoop 生态系统中的附加组件 HDFSHDFS 集群架构HDFS 读写流程HDFS 写流程HDFS 读流程 NameNode 持久化机制 MapReduce底层原理示例 Hadoop 是一个由 Apache 基金会开发的分布式系统基础架构,主要解决海量数…

join查询可以⽆限叠加吗?MySQL对join查询有什么限制吗?

大家好,我是 V 哥。正如主题一样,join查询可以⽆限叠加吗?MySQL对join查询有什么限制吗?理解这些,可以让我们在使用 join时更加游刃有余。 首先可以肯定的是,在 MySQL 中,JOIN 查询不可以无限叠…

vi 编辑器的使用

1 . 复制文件 格式:cp 源文件 目标文件 示例:把 file1.txt 复制一份得到 file2.txt,那么对应的命令就是:cp file1.txt file2.txt 2 . 复制目录 格式:cp -r 源文件夹 目标文件夹 示例:把 3 . 重命名和移动…

Golang | 每日一练 (3)

💢欢迎来到张胤尘的技术站 💥技术如江河,汇聚众志成。代码似星辰,照亮行征程。开源精神长,传承永不忘。携手共前行,未来更辉煌💥 文章目录 Golang | 每日一练 (3)题目参考答案map 实现原理hmapb…

希尔排序:突破插入排序的局限

大家好!今天我们要介绍的是一种改进的插入排序算法——希尔排序(Shell Sort)。希尔排序通过“分组插入”的方式,突破了传统插入排序的局限性,大大提高了排序效率。虽然它不是最理想的排序算法,但由于简单且…

C++和OpenGL实现3D游戏编程【连载23】——几何着色器和法线可视化

欢迎来到zhooyu的C++和OpenGL游戏专栏,专栏连载的所有精彩内容目录详见下边链接: 🔥C++和OpenGL实现3D游戏编程【总览】 1、本节实现的内容 上一节课,我们在Blend软件中导出经纬球模型时,遇到了经纬球法线导致我们在游戏中模型光照显示问题,我们在Blender软件中可以通过…

DAV_postgresql_1

本节开始,进行postgresql数据库的再次熟悉与探索,先从基本的温故吧; psql \l \dt 显示表 当不清楚命令使用时候,使用如下 \? \help ; postgres# \? General \copyright show PostgreSQL usage and distribution terms \crosst…