C语言深入浅出解析二叉树

作者:雪芙花 时间:2022-05-12 11:28:21 

树概念及结构

树是一种 非线性 的数据结构,它是由 n ( n>=0 )个有限结点组成一个具有层次关系的集合
把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的

注意:

  • 有一个特殊的结点,称为根结点,根节点没有前驱结点

  • 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <=m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继 因此,树是递归定义的。

如图:

C语言深入浅出解析二叉树

注意:

  • 树形结构中,子树之间不能有交集,否则就不是树形结构

  • 除了根节点外,每个节点有且只有一个父节点

  • 一棵树N个节点的树有N-1条边

相关概念

如图:

C语言深入浅出解析二叉树

  • 节点的度:一个节点含有的子树的个数称为该节点的度; 如上图: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; // 结点中的数据域
};

如图:

C语言深入浅出解析二叉树

树在实际中的运用(表示文件系统的目录树结构)

C语言深入浅出解析二叉树

二叉树概念及结构

概念

  • 二叉树由一个根节点加上左子树和右子树组成:

  • 二叉树度最大为2(度可以为0,1,2)

  • 二叉树的子树有左右之分,次序不能颠倒(有序树)(没有左树,一定没有右树;有左树,不一定有右树)

C语言深入浅出解析二叉树

需要注意的特殊二叉树

满二叉树:

一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树
也就是说,如果一个二叉树的层数为K,且结点总数是2^k-1,则它就是满二叉树

完全二叉树:

完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的(特殊的完全二叉树)
对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树

二叉树的性质

  • 若规定根节点的层数为 1 ,则一棵非空二叉树的 第 i 层上最多有2^(i-1)个结点

  • 若规定根节点的层数为 1 ,则 深度为 h的二叉树的最大结点数是2^h-1

  • 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=log2(n+1)(是log以2为底,n+1为对数)

二叉树的存储结构

存储结构类型:

顺序存储

顺序结构存储就是使用 数组来存储 ,一般使用数组只适合表示完全二叉树(不完全二叉树有空间的浪费)而现实中使用中只有堆才会使用数组来存储

注:二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树

如图:

C语言深入浅出解析二叉树

链式存储

二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是
链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所
在的链结点的存储地址 。

例:


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; // 当前节点值域
};

来源:https://blog.csdn.net/yin_ming_hui/article/details/123689470

标签:C语言,二叉树,基本操作
0
投稿

猜你喜欢

  • android仿微信联系人索引列表功能

    2023-06-22 17:33:30
  • C# Random类随机函数实例详解

    2021-09-12 04:26:42
  • 简单实现Android本地音乐播放器

    2021-09-04 19:28:28
  • Java数据结构之栈与队列实例详解

    2021-05-29 03:25:13
  • C#泛型的逆变协变之个人理解

    2021-05-28 16:33:03
  • java使用@Transactional时常犯的N种错误

    2021-08-16 01:58:44
  • C#简单实现显示中文格式星期几的方法

    2021-09-08 12:27:05
  • java写卷积神经网络(CupCnn简介)

    2022-12-11 09:33:09
  • jvm调优的几种场景(小结)

    2023-04-11 18:37:04
  • MyBatis-Plus 如何单元测试的实现

    2022-03-02 19:45:08
  • 解决VSCode调试react-native android项目错误问题

    2023-10-14 02:02:11
  • WPF实现动画效果(六)之路径动画

    2022-02-05 01:42:15
  • 5分钟搭建SpringCloud Eureka服务注册中心的实现

    2022-07-12 05:12:42
  • SpringMVC入门实例

    2023-02-04 12:43:48
  • C#方法中参数ref和out详解

    2021-07-19 12:59:32
  • SpringBoot配置mybatis驼峰命名规则自动转换的实现

    2023-07-26 17:47:43
  • Android入门之ActivityGroup+GridView实现Tab分页标签的方法

    2022-11-01 05:38:33
  • java 中Spark中将对象序列化存储到hdfs

    2022-09-17 04:06:18
  • java 实现文件复制和格式更改的实例

    2023-10-21 08:07:49
  • Spring Boot加密配置文件特殊内容的示例代码详解

    2023-09-18 08:47:24
  • asp之家 软件编程 m.aspxhome.com