【初阶数据结构】——二叉树概念及结构

文章目录

前言

1. 树的概念及结构

1.1 树的概念

1.2 树与非树

1.3 树的相关概念

1.4 树的表示

1.5 树在实际中的运用（表示文件系统的目录树结构）

2. 二叉树概念及结构

2.1 概念

2.2 现实中的二叉树

2.3 特殊的二叉树

2.3.1 满二叉树

2.3.1 完全二叉树

2.4 二叉树的性质

2.5 二叉树的存储结构

2.5.1 顺序存储

2.5.2 链式存储

前言

我们在前面文章学到的数据结构：顺序表、链表，不管是单链表还是带头双向循环链表，以及后面的栈和队列。

它们呢，其实都属于一类数据结构——线性表。

那从这篇文章开始：

我们将开始学习数据结构中的非线性结构，今天我们先来学习第一种——二叉树

1. 树的概念及结构

那要学习二叉树，我们首先要知道什么是树。

所以我们先来了解一下数据结构中树的概念及结构。

如果不提数据结构，只谈树，相信大家都不陌生，对吧，谁还没见过树啊。

那数据结构中的树，到底是什么东西呢？

我们一起来看一看。

1.1 树的概念

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

现实生活中的树：

数据结构中的树：

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

除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。

每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。

因此，树是递归定义的。

1.2 树与非树

大家看这3个东西是树吗？

它们不是树。

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

1.3 树的相关概念

下面我们一起来了解一些与树相关的概念：

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的度为6

叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点

非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点

树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推

至于结点的层次呢，其实有两种方案，一种是从0开始，即认为根节点的层次为0，另一种是从1开始。

这两种方案呢其实都可以，但在这里建议大家选择从1开始。

为什么呢？

因为如果我们认为根节点的层次是0，那要表示空树就是-1了。

而如果从1开始，那空树的层次就是0，空树是0 是不是好像更符合我们正常的逻辑啊。

当然只是建议，两种都可以。

树的高度或深度：树中节点的最大层次； 如上图：树的高度为4

堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

森林：由m（m>0）棵互不相交的树的集合称为森林

1.4 树的表示

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

我们这里就简单的了解其中最常用的孩子兄弟表示法。

那什么是孩子兄弟表示法呢？

这种表示方法是一种非常巧妙，非常牛的表示方法。

树中每个结点的结构都是一样的，一个数据域和两个指针域。它的两个指针一个指向自己的第一个孩子结点，另一个指针指向与它相邻的第一个兄弟结点。如果没有孩子或兄弟就指向空。

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

这个表示方法牛的地方就在于，就只需要这两个指针，就可以表示你这个结点有任意多个孩子。

🆗，我们来看一个例子：

1.5 树在实际中的运用（表示文件系统的目录树结构）

Linux系统的目录结构，其实就是一棵树：

2. 二叉树概念及结构

🆗，那了解了树的概念之后，接下来我们就来看一下二叉树。

那什么是二叉树呢？

2.1 概念

一棵二叉树是结点的一个有限集合，该集合:

1. 或者为空
2. 或者由一个根节点加上两棵别称为左子树和右子树的二叉树组成
3. 

由上图我们可以得出：

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

注意⚠：对于任意的二叉树都是由以下几种情况复合而成的：

2.2 现实中的二叉树

我们看两张图片：

图片中的这两棵树其实就是二叉树，可以看成是上下颠倒的二叉树，它们都不存在度大于2的结点。

如果更准确一点的话，应该说它们是满二叉树，就是我们接下来要学习的。

2.3 特殊的二叉树

有两种比较特殊的二叉树：

2.3.1 满二叉树

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

我们来证明一下：

满二叉树每层都是满的，那它每层的结点个数就有这样的关系：

那我们很容易能够看出来，这就是一个等比数列嘛！

所以呢：

如果二叉树总共有k层（即高度为k），那第k层的结点个数就是2^(k-1)个。

那节点的总数就是：

我们根据等比数列的求和公式可以算出来：

结果为：2^k-1个。

大家也可以用错位相减法算也很简单。

那如果一棵满二叉树结点个数为N，假设高度为h，就有这样的关系：

高度为h，所以结点总数就是2^h-1

那么就有2^h-1=N

所以该满二叉树的高度:

2.3.1 完全二叉树

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

这段概念呢说了一大堆，而且也不是很好理解，大家可以不用看。

其实总结一下，可以这样理解二叉树：

二叉树它的前n-1层（结点个数）一定是满的，最后一层可以不满，当然也可以是满的（那此时就是满二叉树了），所以，满二叉树也是一种特殊的完全二叉树。

举个例子：

这就是一棵完全二叉树。

但是，一定要注意⚠：

完全二叉树最后一层的结点从左到右必须是连续的，中间不能间断。

举个栗子：

🆗，那我们接下来再来讨论一下完全二叉树的结点个数：

那满二叉树呢，如果高度确定了，其实它的结点个数就也确定住了。

但是我们说完全二叉树，它的最后一层可以不满，当然也可以是满的。

所以呢，完全二叉树结点个数最多的情况其实就是最后一层也是满的；最少的情况就是最后一层只有一个结点。

注意⚠不要认为是0个，0个的话高度就变了。

因此：

完全二叉树的结点个数应该是一个范围！

那我们就来讨论一下这个范围：

假设一棵完全二叉树高度为h，那它前n-1层的结点个数其实和满二叉树是一样的，都是一个等比数列，公比为2。

那我们其实很容易得出这个范围：

那这个范围我们就得出来了。

2.4 二叉树的性质

接下来我们来看几个二叉树的性质，这些性质在我们做题的过程中可能会用到：

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)个结点。
2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 。

前两个结论经过上面的学习，相信不用给大家过多解释了。

1. 对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2 ,则有 n0＝ n2＋1

性质还没说完，我们先来看几个题：

根据性质3：度为0的结点个数等于度为2的加1，我们很容易得出答案是B。

这道题根据性质，也很好解：

所以答案是A。

一棵完全二叉树的节点数为531个，那么这棵树的高度为（）

A 11

B 10

C 8

D 12

根据我们前面得出的结论，完全二叉树的结点个数是一个范围：

我们可以把高度代进去，得出范围，看531在那个范围中。

答案是B。

1. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log2(n+1) 。
   (p s ：log2(n+1)是log以2为底，n+1为对数)
   这个结论呢，我们在上面也已经证明过了。

2.5 二叉树的存储结构

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

2.5.1 顺序存储

顺序结构存储就是使用数组来存储。

但是呢：

一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。

而现实中使用中只有堆才会使用数组来存储，关于堆我们马上就会讲到。

二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2.5.2 链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。

通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。

链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。

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

这是二叉树的两种存储结构，大家先了解一下，后面我们还会详细讲解。