数据结构之初识二叉树（1）——核心概念入门

前言 嗨，前面我们已经用了3篇文章介绍了栈和队列这两个朋友从数据结构讲到现在，讲了链表，顺序表，栈和队列都是线性表，我们学的还是十分轻松的，今天我们来介绍新的朋友——树，它可不一般，他是非线性结构，难度会有一定的上升，让我们来了解它吧！

链接：栈与队列核心篇（上）：从原理到代码，吃透栈结构 栈与队列核心篇（下）：从基础到进阶，玩转队列设计 数据结构核心：栈 / 队列互转 + 循环队列，三大必刷题型深度拆解

一、树

树是什么呢？是现实的树吗？ 其实是有很大联系的

树的根在下面，而数据结构的树根在上面，如图

在这里插入图片描述

1、树的概念

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

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

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

在这里插入图片描述

2、树的核心术语

以下为一树的结构

在这里插入图片描述

树的核心术语十分多要求我们了解并掌握，树的相关术语与我们的血缘关系十分相近，可以根据血缘关系来记忆

(一)、结点相关术语

• 结点的度：一个结点含有的子树的个数。示例：A的度为6。
• 叶结点（终端结点）：度为0的结点。示例：B、C、H、I等结点。
• 非终端结点（分支结点）：度不为0的结点。示例：D、E、F、G等结点。

(二)、树整体相关术语

• 树的度：一棵树中最大的结点的度。示例：树的度为6（与A的度一致）。
• 结点的层次：从根开始定义，根为第1层，根的子结点为第2层，依次类推。
• 树的高度（深度）：树中结点的最大层次。示例：树的高度为4。
• (三)、亲属关系类术语
• 双亲结点（父结点）：若一个结点含有子结点，则该结点为其子结点的父结点。示例：A是B的父结点。
• 孩子结点（子结点）：一个结点含有的子树的根结点。示例：B是A的孩子结点。
• 兄弟结点：具有相同父结点的结点互称兄弟结点。示例：B、C是兄弟结点。
• 堂兄弟结点：双亲在同一层的结点互为堂兄弟（原文示例标注有误，H、I应为堂兄弟或兄弟需结合层级，按定义修正表述）。
• 结点的祖先：从根到该结点所经分支上的所有结点。示例：A是所有结点的祖先。
• 子孙：以某结点为根的子树中任一结点。示例：所有结点都是A的子孙。

(四)、其他核心术语

• 森林：由m（m>0）棵互不相交的树组成的集合。

3、树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式

• 1、已经知道度

//明确规定树的度为N
#define N 10;
struct TreeNode
{
    int val;
    struct TreeNode* subs[N];
};

但会浪费空间，而且如果不知道树的度就无法储存

• 2、用C++中树的结构

struct TreeNode
{
    int val;
    vector<struct TreeNode*> subs;
};

但我们还没学习，所以这里不利用

• 3、兄弟表示法 这是一个十分天才的思路，用一个指针指向第一个孩子节点，另一个指针指向下一个兄弟节点，是最常用的方法

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

用兄弟表示法这样表示树

在这里插入图片描述

4、树的实际应用

比如电脑中U盘对文件的存储，就是属于多叉树结构

二、二叉树

1、二叉树的概念

所谓二叉树， 是一种重要的树形数据结构，其核心特征是每个节点最多有两个子节点，分别称为左子树和右子树。 一棵二叉树是结点的一个有限集合，该集合

• 1. 或者为空
• 1. 由一个根结点加上两棵别称为左子树和右子树的二叉树组成 结构如图：

  

  在这里插入图片描述

  由图可得：

• 特点：

1. 二叉树不存在度大于2的结点
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

2、现实中的二叉树

在这里插入图片描述

3、特殊的二叉树

（1）满二叉树

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

在这里插入图片描述

为什么节点总数是2k呢？我们可以看出来每一层之间的关系为2倍的等比数列，用等比数列公式，1+2+21+22+23+……+2k-1=2k-1证得

（2）完全二叉树

概念： 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。 如图：

在这里插入图片描述

二者区别就是完全二叉树最后一层不用满，只要连续就行了 注意

在这里插入图片描述

这个不满足连续，所以不是二叉树

4、总结

(1)若规定根结点的层数为1，则一棵非空二叉树的第 i 层上最多有2i-1个结点 (2)若规定根结点的层数为1，则深度为 h 的二叉树的最大结点数是2h (3)对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n0＝n2 ＋1 第3条如图

    🟧 (n2=1)
   /          \
🟧 (n2=1)    🟧 (n2=1)
   /    \       /    \
🔴 (n0) 🔴(n0)🔴(n0)🔴(n0)

三、二叉树的存储方式

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

1、顺序结构

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。

• 二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。 想象的结构

在这里插入图片描述

实际的结构

在这里插入图片描述

我们就会疑惑用数组怎么存储二叉树呀？这就用到了二叉树独特的性质

如果父亲在数组中的下标为：i； 则左孩子在数组中的下标为：2 * i + 1； 则右孩子在数组中的下标为：2 * i + 2 大家可以去结合图验证一下 如果孩子在数组中的下标为：j； 则父亲在数组中的下标为：(j - 1) / 2 ；//因为int类型取整，所以无论 左孩子(（2i+1-1）/2=i) 还是右孩子(2i+2-1)/2=(2*i+1)/2=i， 结果都是对应的父亲

2、链式结构

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

在这里插入图片描述

在这里插入图片描述

结束语

本篇到这里就结束了，主要让大家了解一下树和二叉树的相关概念，如果文章写的有什么问题，希望大家积极在评论区提供建议，下一篇我们就要实现二叉树的顺序结构就是堆，相信大家都有所收获，让我们期待下一篇的精彩内容吧！ 让我们再看一下我们生活中美丽的树吧