【初阶数据结构】树与二叉树:从零开始的奇幻之旅

在这里插入图片描述

初阶数据结构相关知识点可以通过点击以下链接进行学习一起加油!
时间与空间复杂度的深度剖析深入解析顺序表:探索底层逻辑深入解析单链表:探索底层逻辑深入解析带头双向循环链表:探索底层逻辑深入解析栈:探索底层逻辑
深入解析队列:探索底层逻辑深入解析循环队列:探索底层逻辑

本篇将从树与二叉树相关概念进行入手,帮助我们接下二叉树更进一步的学习。

请添加图片描述
Alt

🌈个人主页:是店小二呀
🌈C语言笔记专栏:C语言笔记
🌈C++笔记专栏: C++笔记
🌈初阶数据结构笔记专栏: 初阶数据结构笔记

🌈喜欢的诗句:无人扶我青云志 我自踏雪至山巅
请添加图片描述

文章目录

  • 一、树概念及结构
    • 1.1 树的相关概念
  • 二、树的存储表示
  • 三、二叉树概念
    • 3.1 现实中的二叉树(见到都要拜几下)
  • 四、特殊的二叉树
    • 4.1 不属于完全二叉树的情况
  • 五、二叉树的存储结构
    • 5.1 顺序存储
    • 5.2 父子节点间下标规律关系(重要)
    • 5.3 链式存储
    • 5.4 小总结

一、树概念及结构

树是一种非线性的数据结构,它是由n(n>=0)个有限节点组成一个具有层次关系的集合,然而树在实践中价值不大,但是二叉树实践价值比较大(这种集合称为树的理由,是它是根朝上,而叶朝下,看起来很像树)

  • 有一个特殊的节点,称为根节点,根节点没有前驱节点
  • 除根节点外,其余节点被分成M(M>0)个互不相交的集合T1、T2、....、Tm,其中每一个集合Ti(1<=i<=m)又是一颗结构与树类似的子树。每颗子树的根节点有且只有一个前驱,可有0个或多个后继。
  • 树是递归定义,与此同时需要注意。在树形结构中子树之间不能有交集,否则就不是树形结构

在这里插入图片描述

在这里插入图片描述

1.1 树的相关概念

在这里插入图片描述

  • 节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A的为6
  • 叶节点或终端节点:度为0的节点称为叶节点; 如上图:B、C、H、I…等节点为叶节点
  • 非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G…等节点为分支节点
  • 双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点
  • 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点
  • 兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点
  • 树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6
  • 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推
  • 树的高度或深度:树中节点的最大层次; 如上图:树的高度为4
  • 堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点
  • 节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先
  • 子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
  • 森林:由m(m>0)棵互不相交的树的集合称为森林

二、树的存储表示

由于树状结构相对线性表复杂,存储方式也更加麻烦,既要保存值域,也要保存好结点和结点之间的关系。

以下根据之前知识得到的几种方法

  • 每个孩子都有一个地址,可以通过指针数组存储数据(空间是固定,申请新空间有代价和空间情况问题出现)
  • 对于第一种方法优化,将指针数组改用为顺序表存储孩子,解决了空间固定的问题
  • 推荐常用的解法:左孩子右兄弟法(老大带着老二,老二带着老三,不用双亲累)
typedef int DataType;
struct Node
{
    struct Node* _firstChild1; // 第一个孩子结点
    struct Node* _pNextBrother; // 指向其下一个兄弟结点
    DataType _data; // 结点中的数据域
};

在这里插入图片描述

当然不局限以上几种方式,还有双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法

三、二叉树概念

一颗二叉树是节点的一个有限集合,该集合可能有两种情况

  1. 空树
  2. 由一个根节点加上两颗别称为左子树和右子树的二叉树组成(子树可能为空树)

在这里插入图片描述

从图中可以得出两个结论:

  1. 二叉树不存在度大于2的结点

  2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

注意:对于任意的二叉树都是通过下列几种情况组成的(空树的情况最容易忘记)

在这里插入图片描述

3.1 现实中的二叉树(见到都要拜几下)

在这里插入图片描述

四、特殊的二叉树

  • 满二叉树:一个二叉树,如果每一个层的节点数都达到最大值,则这个二叉树为满二叉树。换言之一个二叉树的层次为K,且节点总数是2K-1,则它就是满二叉树
  • 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出的。对于高度为K,有n个节点的二叉树,当且仅当每一个节点都与高度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

简单概括下:

  • 满二叉树的每一层都是满的

  • 完全二叉树如果高度是n,那么前n-1个是满的,最后一层不一定满,但是从左到右必须是连续

  • 完全二叉树是效率很高的数据结构,满二叉树是一种特殊的完全二叉树

  • 满二叉树是完全二叉树的充分必要条件

在这里插入图片描述

4.1 不属于完全二叉树的情况

这种就是普通的二叉树,从左到右不是连续的。

在这里插入图片描述

五、二叉树的存储结构

二叉树一般可以使用两种结构存储,一种是顺序结构,一种链式结构

5.1 顺序存储

顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是满二叉树会有空间的浪费,对此现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树,在接下来做题我们需要根据物理上是数组,逻辑上是二叉树配合去解出一道题目。

在这里插入图片描述

5.2 父子节点间下标规律关系(重要)

  • leftchild = parent * 2 + 1;

  • rightchild = paretn * 2 +2;

  • parent = (child - 1) / 2;(不区分左右孩子)

  • 对于第三点,个人推理下,leftchild下标拆为leftchild- 11,对于leftchild-1parent下标两倍,对于(child - 1) / 2运算将leftchild拆出来为1部分单独除于2取整数为0,leftchild -1部分可以看成leftchild,而且rightchild与leftchild相差1,由于rightchild = leftchild - 1和通过上面leftchild - 1 ~= leftchild,可以推理出rightchild = leftchild(在进行/2运算,取整数情况下)

5.3 链式存储

二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,后面学到高阶数据结构如红黑树等会用到三叉链

在这里插入图片描述
**加粗样式**

typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
        struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
    struct BinTreeNode* _pParent; // 指向当前节点的双亲
    struct BinTreeNode* _pLeft; // 指向当前节点左孩子
    struct BinTreeNode* _pRight; // 指向当前节点右孩子
    BTDataType _data; // 当前节点值域
}

5.4 小总结

顺序结构存储就是通过数组进行存储,一般使用数组只适合完全二叉树,非完全二叉树就不适合数组结构存储,普通二叉树只适合链式结构存储。但是在现实中使用堆才会使用数组来存储,大部分还是通过链式结构存储。

原因在于:

  1. 首先我们要知道,二叉树拥有其特殊的逻辑结构,不同于其他数据结构适合堆数据的增删查改,因为在于开辟的空间消耗大,逻辑也更加复杂,如果使用如此复杂的结构去存储数据,不是没有多少价值的,这样子不如一开始就采用顺序表进行存储数据。同时一般而言,二叉树的结构是递归式,用非递归实现更加麻烦,
  2. 普通二叉树中可能存储元素密度很低,连续存储的结构会造成大量的空间浪费
  3. 堆是根据"堆属性"来排序,"堆属性"决定了树中结点的位置(在下面堆的介绍有说明)

以上就是本篇文章的所有内容,在此感谢大家的观看!这里是店小二初阶数据结构笔记,希望对你在学习初阶数据结构中有所帮助!
请添加图片描述

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

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

相关文章

数据结构(Java):集合类LinkedList集合类Stack

1、集合类LinkedList 1.1 什么是LinkedList LinkedList的底层是一个双向链表的结构&#xff08;故不支持随机访问&#xff09;&#xff1a; 在LinkedList中&#xff0c;定义了first和last&#xff0c;分别指向链表的首节点和尾结点。 每个节点中有一个成员用来存储数据&…

视频压缩电脑软件,视频压缩电脑怎么操作

在数字媒体时代&#xff0c;视频文件的大小往往让人头疼。如何在不损失画质的情况下压缩视频&#xff0c;成为了许多创作者和普通用户的需求。本文将为你详细介绍电脑压缩软件&#xff0c;让你轻松应对视频压缩任务。 1.下载并安装视频压缩软件。 2.打开软件&#xff0c;选择视…

[leetcode] shortest-subarray-with-sum-at-least-k 和至少为 K 的最短子数组

. - 力扣&#xff08;LeetCode&#xff09; class Solution { public:int shortestSubarray(vector<int>& nums, int k) {int n nums.size();vector<long> preSumArr(n 1);for (int i 0; i < n; i) {preSumArr[i 1] preSumArr[i] nums[i];}int res n…

机遇与挑战并存 券商国际化战略布局关键要素

引言 在全球金融市场不断开放和技术快速进步的背景下&#xff0c;越来越多中资背景的券商开始寻求国际化发展。富途和老虎证券作为先行者&#xff0c;展示了中国券商在出海过程中的巨大潜力和成功经验。鉴于中资在海外设立券商的成功&#xff0c;不少公司也有意愿在海外设立券…

爆款文案管理系统设计

设计一个爆款文案管理系统&#xff0c;目标是帮助营销团队高效地创建、管理并分析吸引人的文案&#xff0c;以提升产品或服务的市场吸引力和销售转化率。以下是一些关键功能和设计考量点&#xff1a; 1. 用户友好界面 简洁直观的界面&#xff1a;确保系统界面清晰&#xff0c…

抖音短视频矩阵管理系统搭建全攻略:功能详解与实战应用

在短视频时代&#xff0c;抖音已经成为众多企业、网红、个人创作者不可或缺的传播平台。然而&#xff0c;如何高效管理多个抖音账号&#xff0c;实现内容、数据、粉丝的全方位掌控&#xff0c;成为了摆在大家面前的一道难题。本文将为大家深入解析抖音短视频矩阵管理系统的搭建…

项目管理工具评测:2024年国内外最顶级的10款项目管理工具排行

国内外涌现出众多优秀的项目管理工具&#xff0c;它们各自在功能、易用性、集成能力等方面展现出独特优势。以下是国内外顶级的10款项目管理工具&#xff1a; 一、进度猫 推荐理由&#xff1a;进度猫以其直观的任务管理和进度跟踪功能&#xff0c;成为许多团队和项目的首选…

C++入门 模仿mysql控制台输出表格

一、 说明 控制台输出表格&#xff0c;自适应宽度 二、 源码 #include <iostream> #include <map> #include <string> #include <vector>using namespace std;void printTable(vector<vector<string>> *pTableData) {int row pTableDa…

Leetcode104.求二叉树的最大深度

题目描述 递归法 class Solution {public int maxDepth(TreeNode root) {if (root null) { //帮助下面的else语句判空return 0;} else {int leftHeight maxDepth(root.left);int rightHeight maxDepth(root.right);/*** 要注意的点* 1. 这个return是写在else语句里面的&am…

ABeam News | FY25 ABeam德硕大中华区入社式,飞往崭新航向!

FY25 ABeam大中华区入社式 7月1日&#xff0c;51名 ABeam大中华区新生在艾宾信息技术开发&#xff08;上海&#xff09;有限公司大连分公司&#xff08;以下简称TDC&#xff09;报到&#xff0c;我们为他们的到来准备了隆重的入社仪式&#xff0c;并举办了热情而又温馨的欢迎晚…

通过图像高频信息保留图像细节,能保留多少细节-Comfyui

&#x1f9e8;前情提要 如果还不了解comfyui中图像高频信息保留细节的内容&#xff0c;可以参考上一篇文章&#xff1a; 图像中高频信息、低频信息与ComfyUI中图像细节保留的简单研究-CSDN博客 这次主要是简单测试下保留图像细节&#xff0c;能保留到什么程度&#xff1b; …

JavaScript(7)——数组

JavaScript中数组的用法与Java差不多&#xff0c;但还是有一些区别 声明数组 语法: let 数组名 [数据1,数据2,数据...] let arr new Array(数据1,数据2,...数据n) 添加数据 数组.push()方法将一个或多个元素添加到数组末尾&#xff0c;并返回该数组新长度 <script>…

【AI大模型新型智算中心技术建设白皮书 2024】

文末有福利&#xff01; 一、新算效——重塑计算架构 1.1 下一代 AI 芯片设计思路 以 GPU 为 代 表 的 高 性 能 并 行 计 算 芯 片 架 构 和 以 针 对 AI 领 域 专 用 加 速&#xff08;DSA, Domain Specific Architecture&#xff0c;DSA&#xff09;为代表的芯片架构是目…

麦克风领夹式的哪个牌子最好,无线领夹麦克风十大品牌

在直播和自媒体行业迅速崛起的今天&#xff0c;无线麦克风因其便携性和实用性成为了视频制作和直播带货中不可或缺的工具。面对市场上从几十元到几千元不等的无线麦克风&#xff0c;作为一位资深直播运营专家&#xff0c;我深知选择合适的设备对于提升直播质量和观众体验的重要…

排序相关算法--1.插入排序+冒泡排序回顾

1.基本分类 2.插入排序 特点&#xff1a;有实践意义&#xff08;例如后期快排的优化&#xff09;&#xff0c;适应性强&#xff0c;一般不会到时间复杂度最坏的情况。 将第一个元素视为已经排好序的序列。取出下一个元素&#xff0c;在已经排好序的序列中从后往前比较&#xf…

3SRB5016-ASEMI逆变箱专用3SRB5016

编辑&#xff1a;ll 3SRB5016-ASEMI逆变箱专用3SRB5016 型号&#xff1a;3SRB5016 品牌&#xff1a;ASEMI 封装&#xff1a;SGBJ-5 批号&#xff1a;2024 现货&#xff1a;50000 最大重复峰值反向电压&#xff1a;1600V 最大正向平均整流电流(Vdss)&#xff1a;50A 功…

C 语言中如何实现字符串的拼接?

&#x1f345;关注博主&#x1f397;️ 带你畅游技术世界&#xff0c;不错过每一次成长机会&#xff01; &#x1f4d9;C 语言百万年薪修炼课程 【https://dwz.mosong.cc/cyyjc】通俗易懂&#xff0c;深入浅出&#xff0c;匠心打磨&#xff0c;死磕细节&#xff0c;6年迭代&…

GB28181设备如何添加

简介 此篇描述视频网关&#xff08;中间件&#xff09;接入大华、海康、ONVIF设备&#xff08;NVR、摄像头&#xff09;、GB28181设备步骤和流程。 阅读本文档之前建议先阅览视频网关&#xff08;中间件&#xff09;用户使用手册。 接入方式和说明 视频网关&#xff08;中间…

捷配笔记-如何设计PCB板布线满足生产标准?

PCB板布线是铺设连接各种设备与通电信号的路径的过程。PCB板布线是铺设连接各种设备与通电信号的路径的过程。 在PCB设计中&#xff0c;布线是完成产品设计的重要步骤。可以说&#xff0c;之前的准备工作已经为它做好了。在整个PCB设计中&#xff0c;布线设计过程具有最高的极限…

网关、DHCP协议、ip地址、子网掩码简单介绍

参考文章&#xff1a;https://baike.baidu.com/item/%E7%BD%91%E5%85%B3/98992?frge_ala https://baike.baidu.com/item/DHCP%E6%9C%8D%E5%8A%A1%E5%99%A8/9956953?fromModulelemma_inlink https://blog.csdn.net/weixin_58783105/article/details/135041342 https://blog.cs…