数据结构入门(C语言版)二叉树概念及结构(入门)

news/2024/4/25 0:08:13/

在这里插入图片描述

二叉树概念及结构(入门)

  • 树的概念及结构
    • 1.树的概念及结构
      • 1.1 树的概念
      • 1.2 树的相关知识
      • 1.3 树的结构体表示
      • 1.4 树的实际运用
    • 2.二叉树概念及结构
      • 2.1 二叉树的概念
      • 2.2 现实中的二叉树
      • 2.3 特殊的二叉树
      • 2.4 二叉树的性质
      • 2.5 二叉树的存储结构
  • 结语

树的概念及结构

1.树的概念及结构

1.1 树的概念

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
☆有一个特殊的结点,称为根结点,根节点没有前驱结点
☆除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继
☆因此,树是递归定义的。
请添加图片描述
请添加图片描述
tips:树形结构中,子树之间不能有交集,否则就不是树形结构
在这里插入图片描述
☆子树是不相交
☆除了根节点外,每个结点有且仅有一个父节点
☆一颗N个结点的树有N-1条边

1.2 树的相关知识

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

1.3 树的结构体表示

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既保存值域,也要保存结点和结点之间的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。这里展示最常用的孩子兄弟表示法

typedef int DataType;
struct Node
{struct Node* Child; // 第一个孩子结点struct Node* Brother; // 指向其下一个兄弟结点DataType data; // 结点中的数据域
};

请添加图片描述

1.4 树的实际运用

比如操作系统中的目录树结构
图片来自网络

2.二叉树概念及结构

2.1 二叉树的概念

一棵二叉树是结点的一个有限集合,该集合:
☆ 或者为空
☆ 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
二叉树
请添加图片描述
请添加图片描述
从上图可以看出:
☆二叉树不存在度大于2的结点
☆二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
tips:对于任意的二叉树都是由以下几种情况复合而成的:
请添加图片描述

2.2 现实中的二叉树

请添加图片描述

2.3 特殊的二叉树

☆**满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是 ,则它就是满二叉树。
在这里插入图片描述
该图来自百度百科
完全二叉树:**完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
在这里插入图片描述
该图来自百度百科

2.4 二叉树的性质

★若规定根节点的层数为1,则一棵非空二叉树的第x层上最多有2^(x-1)个结点.
★若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2^h-1.
★对任何一棵二叉树, 如果度为0其叶结点个数为N0, 度为2的分支结点个数为N2,则有N0=N2+1
★ 若规定根节点的层数为1,具有n个结点的满二叉树的深度h=log2(n+1)(2为底,n+1为对数)
★对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为x的结点有

  1. 若x>0,i位置节点的双亲序号:(x-1)/2;x=0,x为根节点编号,无双亲节点
  2. 若2x+1<n,左孩子序号:2x+1,2x+1>=n否则无左孩子
  3. 若2x+2<n,右孩子序号:2x+2,2x+2>=n否则无右孩子

2.5 二叉树的存储结构

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。
★顺序存储
顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储,关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。
★ 链式存储
二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,数据结构入门学习一般都是二叉链,高阶数据结构会涉及如红黑树等会用到三叉链。
二叉链的结构体表示:

typedef int BTDataType;
struct BinaryTreeNode
{struct BinTreeNode* Left; // 指向当前节点左孩子struct BinTreeNode* Right; // 指向当前节点右孩子BTDataType data; // 当前节点值域
}

三叉链的结构体表示:

struct BinaryTreeNode
{struct BinTreeNode* Parent; // 指向当前节点的双亲struct BinTreeNode* Left; // 指向当前节点左孩子struct BinTreeNode* Right; // 指向当前节点右孩子BTDataType data; // 当前节点值域
}

结语

在下一期的更新中,作者会写到堆的应用和实现,在这篇文章中的理论知识摘录于网络,有兴趣的小伙伴可以关注作者,如果觉得内容不错,请给个一键三连吧,蟹蟹你哟!!!

制作不易,如有不正之处敬请指出
感谢大家的来访,UU们的观看是我坚持下去的动力
在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!
请添加图片描述


http://www.ppmy.cn/news/46848.html

相关文章

根据 cadence 设计图学习硬件知识 day01了解腾锐 D2000芯片

1. 首先了解 腾锐 D2000 1.介绍 腾锐D2000 芯片 D2000芯片集成8个飞腾自主研发的新一代高性能处理器内核FTC663&#xff0c;采用乱序四发射超标量流水线&#xff0c;兼容64位ARMV8指令集并支持ARM64和ARM32两种执行模式&#xff0c;支持单精度、双精度浮点运算指令和ASIMD处…

设计模式 -- 门面模式

前言 月是一轮明镜,晶莹剔透,代表着一张白纸(啥也不懂) 央是一片海洋,海乃百川,代表着一块海绵(吸纳万物) 泽是一柄利剑,千锤百炼,代表着千百锤炼(输入输出) 月央泽,学习的一种过程,从白纸->吸收各种知识->不断输入输出变成自己的内容 希望大家一起坚持这个过程,也同…

100种思维模型之非共识思维模型-48

某一件事或者某一个环境当中&#xff0c;绝大多数人往右走&#xff0c;而你 发现真正的路是左边 的时候&#xff0c;该怎么选择&#xff1f; 往左边走&#xff0c;做非共识但正确的事&#xff0c;因为一旦你的真的是对的&#xff0c;你将会得到一切。 非共识思维模型是一个提…

集群和分布式

本文以即时通讯软件&#xff08;IM&#xff09;为例&#xff0c;介绍单机、集群、分布式的区别&#xff0c;以及它们各自的优缺点。 假设现在开发一款IM&#xff0c;刚开始业务比较简单&#xff0c;用户量也较少&#xff0c;我们将服务部署在一台单机服务器上足矣。软件开发过程…

std::regex正则表达式

std::match_results &#xff08;匹配的结果存入其中&#xff09; result[0]是完整的文本&#xff0c;result[1]是第一个分组匹配的数据。如果正则表达式有n个分组&#xff0c;match_results的size也就是n1个 This is a specialized allocator-aware container. It can only …

【FPGA实验4】举重比赛机制

举重比赛有三名裁判&#xff0c;当运动员将杠铃举起后&#xff0c;须有两名或两名以上裁判认可&#xff0c;方可判定试举成功&#xff0c;若用A、B、C分别代表三名裁判的意见输入&#xff0c;同意为1&#xff0c;否定为0;F为裁判结果输出&#xff0c;试举成功时F1&#xff0c;试…

逍遥自在学C语言 | 位运算符~的高级用法

前言 在上一篇文章中&#xff0c;我们介绍了^运算符的高级用法&#xff0c;本篇文章&#xff0c;我们将介绍~ 运算符的一些高级用法。 一、人物简介 第一位闪亮登场&#xff0c;有请今后会一直教我们C语言的老师 —— 自在。 第二位上场的是和我们一起学习的小白程序猿 ——…

Direct3D 12——计算着色器——计算着色器概念

计算着色器虽然是一种可编程的着色器&#xff0c;但Direct3D并没有将它直接归为渲染流水线中的一部分。虽然如此&#xff0c;但位于流水线之外的计算着色器却可以读写GPU资源。从本质上来说&#xff0c;计算着 色器能够使我们访问GPU来实现数据并行算法&#xff0c;而不必渲染出…

5.Spring Cloud (Hoxton.SR8) 实战笔记—项目中细节实现 约束 注意事项、模块难点总结

本文目录如下&#xff1a; 二、项目中细节实现 & 约束 & 注意事项判断字符串是否为空&#xff1f;入参 Num 字段转换为 num 的问题&#xff1f;通过 Java 获取时间 (Date类型) 并插入数据库&#xff1f;神坑: baseMapper.selectById(String str)之坑?AES 实现加密函数…

[Eigen中文文档] 切片和索引

专栏总目录 本文目录 概述基本的切片编译时的大小和步长倒序索引序列自定义索引列表 英文原文(Slicing and Indexing) 本文介绍了如何使用操作运算符operator()索引行和列的子集。该 API 在 Eigen 3.4 中引入。它支持 block API 提供的所有功能。特别是&#xff0c;它支持切片…

查询练习:条件加组筛选

查询 student 表中至少有 2 名男生的 class 。 -- 查看学生表信息 SELECT * FROM student; ---------------------------------------- | no | name | sex | birthday | class | ---------------------------------------- | 101 | 曾华 | 男 | 1977-09-01 | 95…

vue 动态组件

一见如故 // 一般配合<keep-alive>组件&#xff0c;避免反复重新渲染dom <keep-alive><component :is"com"></component> </keep-alive> <script> import Left from ./LeftComponent.vue import Right from ./RightComponent.v…

Ae:自动定向

Ae 菜单&#xff1a;图层/变换/自动定向 Auto-Orient 快捷键&#xff1a;Ctrl Alt O 自动定向 Auto-Orient是 Ae 图层中的一个附加的、隐藏实现&#xff08;不会在时间轴面板上更改属性的值&#xff09;的功能&#xff0c;它可以使得图层自动旋转或改变方向以朝向指定的运动路…

【Linux阅读笔记】LinuxC一站式编程1-程序基本概念与gdb调试

目录 程序基本概念配置开发环境第一个程序C 复习 gdb单步执行与跟踪断点观察点段错误 程序基本概念 使用 ubuntu22.0 作为演示环境&#xff08;vmware 虚拟机搭设&#xff09; 配置开发环境 配置完基础开发环境后&#xff0c;可以直接下载一个 vscode 作为初始 LDE 使用&#x…

机器学习 day03(成本函数,简化后的和一般情况下的成本函数)

1. 成本函数 平方误差成本函数是最通常用于线性回归的成本函数最终&#xff0c;我们要找到一组w和b&#xff0c;让j函数的值最小误差&#xff1a;ŷ - y 2. 简化后的平方误差成本函数&#xff0c;即b 0 当w 1时&#xff0c;f(x) x&#xff0c;J(1) 0 左侧为f(x)函数&am…

Python 图像处理实用指南:11~12

原文&#xff1a;Hands-On Image Processing with Python 协议&#xff1a;CC BY-NC-SA 4.0 译者&#xff1a;飞龙 本文来自【ApacheCN 计算机视觉 译文集】&#xff0c;采用译后编辑&#xff08;MTPE&#xff09;流程来尽可能提升效率。 当别人说你没有底线的时候&#xff0c;…

程序员 如何避免职场危机,打造自己稀缺性

你在职场上如何又脱颖而出 你唯一的办法就干嘛 找一找怎么才能构建我自己的稀缺性 我经过我 多年的工作和有观察的体验 化是什么呢 从技术迭代进步的角度来说 因为软件越来a p i化 个人的能力被解脱了 一定会向上下有延伸 因为当你做一块 以前是一年做下来时间只需要一个月 是一…

(一)Linux:自由、开放、灵活的操作系统内核

目录 一、Linux的发展史 二、linux的开源 三、目前的现状 四、企业应用现状 五、发行的版本 六、安装与使用 七、利用云服务器配置Linux环境 一、Linux的发展史 Linux是一款由林纳斯托瓦兹&#xff08;Linus Torvalds&#xff09;开发的操作系统内核&#xff0c;它的发布…

windows开启自启动jar包

1.新建txt文本文档 2.复制以下内容&#xff0c;并记得修改 appName 到自己jar包所在目录 并修改jar包名称 3.重命名文本文档.txt为 &#xff08;自己起名字&#xff09;.bat (注&#xff1a;修改成.bat文件&#xff0c;名字自己起) echo off setlocal set appNameD:/tes…

Qt QList 详解:从底层原理到高级用法

目录标题 引言&#xff1a;QList 的重要性与应用场景&#xff08;Introduction: The Importance and Application Scenarios of QList&#xff09;QList的常用接口QList和std::listQList 使用场合迭代器&#xff1a;遍历 QList 中的元素&#xff08;Iterators: Traversing Elem…