树的基本概念与二叉树

文章目录

  • 树的基本概念与二叉树
    • 一、树的概念和结构
      • 1. 树的概念
      • 2. 树的相关概念
    • 二、树的存储
      • 1. 左孩子右兄弟表示法
      • 2. 双亲表示法
    • 三、二叉树
      • 1. 特殊的二叉树
        • 1.1 满二叉树
        • 1.2 完全二叉树

树的基本概念与二叉树

一、树的概念和结构

1. 树的概念

树是一种非线性的数据结构,它是由 n (n≥0) 个有限结点组成一个具有层次关系的集合。之所以称之为"树",是因为它的结构看起来像一棵倒挂的树,根朝上,叶子朝下。树具有以下特点:

  • 有一个特殊的节点,称为根节点,根节点没有前驱节点。
  • 除根节点外,其余节点被分成 M 个 (M>0) 互不相交的集合。
  • 树是递归定义的。
  • 在树形结构中,子树之间不能有交集,否则就不是树形结构。

2. 树的相关概念

  • 节点的度: 一个节点含有的子树的个数称为该节点的度。
  • 叶节点或终端节点: 度为 0 的节点称为叶节点。
  • 非终端节点或分支节点: 度不为 0 的节点。
  • 双亲节点或父节点: 若一个节点含有子节点,则这个节点称为其子节点的父节点。
  • 孩子节点或子节点: 一个节点含有的子树的根节点称为该节点的子节点。
  • 兄弟节点: 具有相同父节点的节点互称为兄弟节点。
  • 树的度: 一棵树中,最大的节点的度称为树的度。
  • 节点的层次: 从根节点开始定义,根为第一层,根的子节点为第二层,以此类推。
  • 树的高度或深度: 树中节点的最大层次。
  • 堂兄弟节点: 双亲在同一层的节点互为堂兄弟。
  • 节点的祖先: 从根到该节点所经分支上的所有节点。
  • 子孙: 以某节点为根的子树中任一节点都称为该节点的子孙。
  • 森林: 由 m (m>0) 棵互不相交的树的集合称为森林。

需要注意的是:

  • 当树为空树时,树的高度/深度通常设为 0。
  • 子树之间是不能相交的。
  • 除了根节点外,每个节点有且仅有一个父节点。
  • 一棵拥有 N 个节点的树有 N-1 条边。

二、树的存储

1. 左孩子右兄弟表示法

左孩子右兄弟表示法是树形结构的一种常见且最优的存储方式。其结点结构如下:

struct TreeNode {
    int val;
    struct TreeNode* firstChild;    // 指向最左边的第一个孩子结点
    struct TreeNode* nextSibling;   // 指向当前节点右边一个兄弟结点
};
  • firstChild: 指向最左边的第一个孩子结点,如果没有则指向 null。
  • nextSibling: 指向当前节点右边的一个兄弟节点,如果没有则指向 null。

2. 双亲表示法

双亲表示法不存储指向孩子的指针,只存储指向父亲的指针或下标。

  • 不支持从根找孩子,只支持从孩子找父亲。
  • 判断两个节点是否在同一棵树中,可以通过寻找它们的根节点是否相同来确定。
  • 并查集就是使用双亲表示法实现的。
  • 根节点没有父亲,所以通常存储 -1。

三、二叉树

二叉树是一种特殊的树形结构,它实行了"计划生育",每个节点最多只能有两个孩子。二叉树具有以下特点:

  • 二叉树中不存在度大于 2 的节点,每个节点最多有两个孩子,也可以只有一个孩子或没有孩子。
  • 二叉树由一个根节点以及两棵分别称为左子树和右子树的二叉树组成。
  • 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树。
  • 二叉树有多种情况:空树、只有根节点、只有左子树、只有右子树以及左右子树都存在。

1. 特殊的二叉树

1.1 满二叉树

满二叉树是指一棵二叉树的每一层节点数都达到最大值。对于一棵高度为 h 的满二叉树,它一共有 (2^h)-1 个节点。证明如下:

设 F(h) 表示高度为 h 的满二叉树的节点总数,则有:
F(h) = 2^0 + 2^1 + 2^2 + ... + 2^(h-2) + 2^(h-1)

这是一个等比数列,其前 n 项和公式为:
Sn = (a1 * (1 - q^n)) / (1 - q)

代入 a1 = 1, q = 2, n = h,得:
F(h) = (2^h) - 1

另一种证明方法是错位相减法:

  • `2F(h) = 2^1 + 2^2 + 2^3 + … + 2^(h-1) + 2^h
  • F(h) = 2^0 + 2^1 + 2^2 + ... + 2^(h-2) + 2^(h-1)
    F(h) = 2^h - 2^0 = 2^h - 1
1.2 完全二叉树

完全二叉树是由满二叉树引出来的,其效率很高。满二叉树是完全二叉树的一种特殊情况。

假设二叉树的高度为 h,则完全二叉树满足以下条件:

  • 前 h-1 层都是满的。
  • 第 h 层不一定满,但第 h 层的节点从左到右是连续的。

对于高度为 h 的完全二叉树,其节点数的范围是 [2^(h-1), 2^h - 1]

以上就是对树的基本概念以及二叉树的介绍。树是一种非常重要且常用的数据结构,在计算机科学领域有着广泛的应用。深入理解树的概念和特性,对于解决实际问题和优化算法设计都有很大帮助。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Liunx进程信号

进程信号 进程信号什么是信号liunx信号种类 前后台进程前后台进程的概念 进程信号的产生键盘产生 阻塞信号信号的捕捉用户态和内核态 信号的捕捉函数 进程信号 什么是信号 信号是Unix、类Unix以及其他POSIX兼容的操作系统中进程间通讯的一种有限制的方式。它是一种异步的通知…

计算机专业,不擅长打代码,考研该怎么选择?

考研其实和你的代码能力关系不大 所以在选学校以前可以看看有哪些学校复试是要求上机撸代码的,可能会要求比较严 初试真的不用担心代码问题,我也是基本零编程能力就开始备考考研的... 本人双非科班出身备考408成功上岸,在这里也想给想考40…

先登杯·14天创作挑战营·第④期~ 等你来战!

文章目录 ⭐️ 活动介绍⭐️ 活动详情⭐️ 活动奖品⭐️ 活动流程​⭐️ 评审规则⭐️ 报名&投稿注意事项⭐️ 活动组织 ​ 活动报名入口:https://bbs.csdn.net/topics/618374514 本次活动与官方活动及其他博主的创作型活动并不冲突! ​ ​ ⭐️…

练习 22 Web [极客大挑战 2019]BuyFlag

php弱类型比较,注意Cookie值,php利用数组赋值进行绕过,科学计数法 很明显是弱类型比较,之前的练习题已经遇到过 构造password404adsffd,后面随便什么字母都行 然后 money100000000 然后在student这里卡了很久,post…

python解决既约分数(gcd)

题目: 如果一个分数的分子和分母的最大公约数是1,这个分数成为既约分数。例如3/4、1/8、7/1、都是既约分数。请问,有多少个既约分数,分子和分母都是1到2020之间的整数(包括1和2020)? 分析&#…

Leetcode 17.电话号码的字母组合

题目 思路 输入的digits有几个数就有几层。 一层中有几个数则取决于输入的数字对应的字母有几个。 1.确定递归函数的返回值及参数: 其实参数不是一开始就确定好的,而是你在写递归函数的时候缺啥,就往进去传啥。 这里我就直接全部写出来。…

基于单片机的智能报站系统仿真设计

**单片机设计介绍,基于单片机的智能报站系统仿真设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的智能报站系统仿真设计概要是关于采用单片机技术实现公交车报站功能的系统设计概述。以下是对该设计的…

基于Android studio的二手交易平台--原创

🍅文章末尾有获取完整项目源码方式🍅 目录 一、实现介绍 视频演示 1.1 启动页实现 1.2登录页 1.3注册页 1.4忘记密码 1.5首页 1.6发布页 1.7我的发布 1.8我的收藏 1.9详情页 1.10修改页面 1.11我的页面 ​编辑 二、获取源码 一、实现介…

MATLAB——知识点备忘

最近在攻略ADC建模相关方面,由好多零碎的知识点,这里写个备忘录。 Matlab 判断一个数是否为整数 1. isinteger 函数 MATLAB中,可以使用 isinteger 函数来判断一个数是否为整数,例如:要判断x是否为整数可以采用以下代…

DXP实验3-单片机时钟显示系统的层次原理图设计

目录 一,自上而下的子母图设计 1,绘制层次式电路母图 1)工程及原理图创建和保存 2)开始绘制层次式母图main.SchDoc 2,绘制图纸符号 1)properties选项卡 2)designator标号 3)filename文件名 4&…

[WinForm开源]原神混池模拟器-蒙德篇:软件的基本介绍、使用方法、常见问题解决与代码开源

首先先和各位旅行者道个歉&#xff0c;混池都过去这么久了才把软件开发好并发布出来 >_< 创作目的&#xff1a;为给各位旅行者&#xff08;当然包括我自己&#xff09;估测混池抽取的出货率以及让各位旅行者可以过手瘾&#xff0c;故开发了此项目作为参考。 创作说明&am…

【C++】C++中的stack和queue

一、概述 本篇blog写明了介绍的是STL(标准模板库)中的stack和queue&#xff0c;栈和队列虽然在处理数据的方式上有明显的不同&#xff0c;但它们作为操作受限的线性数据结构&#xff0c;在学习和应用中经常被放在一起讨论&#xff0c;以便更全面地理解数据结构的概念和使用。 在…

VMware ESXi 6.7

1.浏览器中输入地址&#xff0c;进入管理界面 2.选择 存储 右击浏览&#xff0c;创建新的目录 3.点击 上载 &#xff0c;选择镜像文件 4.等待上载完成 5.点击 虚拟机-新建虚拟机 6.进入新建虚拟机界面 7.进入Windows安装界面 8.安装VMware Tools

AI头像背景替换多功能图片编辑器

本软件运用AI技术&#xff0c;可以轻松修改人像衣着外观与背景环境&#xff0c;支持图片延伸功能&#xff0c;还原度自然。同时也支持扣图及替换背景&#xff0c;图像特效处理和动画渲染等功能&#xff0c;是很推荐的一款图像处理软件。 软件介绍&#xff1a; 它是一款…

归并排序详解(非递归)

感谢各位大佬的光临&#xff0c;希望和大家一起进步&#xff0c;望得到你的三连&#xff0c;互三支持&#xff0c;一起进步 个人主页&#xff1a;LaNzikinh-CSDN博客 收入专栏&#xff1a;http://t.csdnimg.cn/LJ2J2 文章目录 前言一.归并排序二.代码实现归并排序&#xff08;递…

【6】单向循环链表

【6】单向循环链表 1、单向循环链表2、add(int index, E element)3、删除 1、单向循环链表 &#x1f58a; 在单向链表的基础上&#xff0c;尾节点的 next 指向头节点 2、add(int index, E element) &#x1f58a; 往尾部添加的代码不用修改&#xff08;和单向链表一样的&am…

华为ensp中基本acl 原理及配置命令(详解)

作者主页&#xff1a;点击&#xff01; ENSP专栏&#xff1a;点击&#xff01; 创作时间&#xff1a;2024年4月5日10点45分 基本ACL的简介 华为ensp中的基本acl是指华为设备中用于控制网络访问的访问控制列表的其中一种类型。基本acl可以根据数据包的源IP地址进行过滤&#…

备战蓝桥杯---多路归并与归并排序刷题

话不多说&#xff0c;直接看题 1. 我们考虑一行一行合并&#xff0c;一共m次&#xff0c;我们合并两个并取前n小&#xff0c;那么我们怎么取&#xff1f; 我们采用分组的思想&#xff1a; 我们选第一列的min,然后把后面那个再纳入考虑&#xff0c;用优先队列实现即可。 下面…

今年考研是太卷了还是太水了,为什么分数线都高的离谱?

25考研的备考形势&#xff0c;势必跟以前不一样了&#xff01; 有些人问&#xff0c;分数线那么高&#xff0c;是不是题目太水了&#xff1f; 问的人肯定不是24考生。 24的题&#xff0c;也就政治正常一点。 其它的&#xff0c;英语难上热搜&#xff0c;数学难度空前&#x…

04---webpack编写可维护的构建配置

01 构建配置抽离成npm包&#xff1b; 意义&#xff1a;通用性&#xff1a; 业务开发者无需关注构建配置 统一团队构建脚本可维护性&#xff1a;构建配置合理的拆分 质量&#xff1a;冒烟测试 单元测试 持续集成构建配置管理的可选方案&#xff1a;1 通过多个配置文件管理不同…