【数据结构】树与二叉树——二叉树的概念

二叉树的概念

导读

大家好，很高兴又和大家见面啦！！！

在上一篇的内容中，我们介绍了树的一些基本概念、重要术语以及树的基本性质。通过上一篇内容的学习，相信大家都已经对树这种数据结构有了一个初步认识，并且能够区分度为m的树与m叉树。

要进一步的认识树这种数据结构的话，我们还是需要从逻辑结构、存储结构以及数据的运算三要素出发，来逐步认识树。

从今天的内容开始，我们将以二叉树这种特殊的树形结构为例，来逐步学习数据结构的三要素。下面我们就来开始进入的内容吧！！！

一、二叉树的定义及其主要特性

二叉树是一种特殊的树形结构，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

1.1 二叉树的定义

这里我们需要注意的是二叉树的左右子树可以都为空子树，也可以是其中一棵为空子树，如下所示：

对于m叉树而言，树中的所有结点的度都是<=m，同理，二叉树中，所有结点的度都是<=2，因此二叉树中每一个结点作为根组成的树都是二叉树。

1.2 二叉树的主要特性

二叉树这种特殊的树形结构，它具有以下独有的特性：

二叉树的组成有三个部分，从左到右依次是：左子树、根结点、右子树；
二叉树的左右次序是确定的，并且二叉树的左右子树不能进行互换，因此二叉树是一棵有序树；
二叉树结点的度<=2，因此二叉树可以为空树；
二叉树的左右子树也是二叉树；

与二叉树比较相似的就是度为2的有序树，其基本形态如下所示：

由上图可知，其基本特性可总结为以下几点：

度为2的有序树的组成部分有两部分：分支结点（度>0的结点）、叶结点（度=0的结点）；
度为2的有序树的左右次序是相较于另一个孩子而言，因此当树中存在度为1的结点时，该结点的孩子结点没有左右之分；
度为2的有序树中至少要有一个度为2的结点，因此其结点数量最少为3；
度为2的有序树中并不是所有结点的度都为2，因此其子树可能是度为1的树和度为0的树；

由此我们可以看到这二者的区别有以下几点

组成部分不同：二叉树是根据结点的位置划分为3部分：左子树、根结点和右子树；度为2的树则根据结点的度划分为2部分：分支结点和叶结点；
结点数量不同：二叉树中结点数量可以为0，即二叉树可以为空树；度为2的树中最少要有一个结点的度为2，因此度为2的树的结点最少为3；
子树的性质不同：二叉树的子树同样也是二叉树；度为2的子树可以是度为0的树、度为1的树和度为2的树；

二、特殊的二叉树

在了解了二叉树的定义和基本特性之后，下面我们来看一下几种特殊的二叉树；

2.1 满二叉树

2.2 完全二叉树

下面我们通过图像来进一步的理解，如下所示：

当我们将其从1开始进行编号时，我们不难得到以下二叉树：

从图中可以看到，编号为13的结点只有左孩子，并且所有大于13的结点全部都是叶节点；而对于14号结点而言，它本身就是叶结点，从图中可以看到，所有编号大于14的结点均为叶结点；因此我们不难得到一个新的结论：

对于高度为h的完全二叉树，当编号为i的结点只有左孩子或者该结点为叶结点时，编号大于i的结点均为叶结点；

那如果是从0开始编号又会如何呢？如下所示：

可以看到，此时该完全二叉树的结点总数为26，编号为12的结点只有左孩子，所有编号大于12的结点均为叶结点，所有编号不超过12的结点均为分支结点。因此前面得到的结论在这里也同样适用只不过稍有不同，如下所示：

其实不管是从0开始编号还是从1开始编号，只要是对于结点数为n的完全二叉树，当对树中的结点从上到下，从左到右依次进行从小到大的编号时，结点的编号一定满足下列结论：

对于最后一个结点n而言，所有编号不大于其父结点的编号的结点均为分支结点，所有编号大于其父结点编号的结点均为叶结点；

细心的朋友会发现对于结点数为n的完全二叉树，还有一条非常重要的结论：

当n为偶数时，最后一个结点一定是左孩子，其父结点的度一定为1；
当n为奇数时，最后一个结点一定是右孩子，树中不存在度为1的结点；

完全二叉树的相关结论对我们后面的学习会非常重要，因此，建议大家熟读一下这些结论，当然，不建议大家死记硬背。如果在考试时遇到了这些问题，完全可以现场将这些结论通过画图推导出来，大家只要理解这些结论是如何得到的即可。

2.3 二叉排序树

定义：左子树上的所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字；左子树和右子树又各是一棵二叉排序树。

二叉排序树（Binary Search Tree）又称为二叉搜索树或者二叉查找树，英文缩写为BST。这个树在后面的学习中也是一个需要重点关注的树，这里我们同样是对其简单的做个介绍。

BST的定义中所提到的关键字，和我们在C语言中学习的关键字是有区别的，我们目前可以简单的理解为就是二叉树的各个结点中存储的内容。在BST中结点存储的内容满足左子树<根结点<右子树，以整型为例，如下所示：

在上图中我们不难发现，在BST中如果一个结点存在左孩子，那么左孩子中存储的内容一定小于该结点存储的内容，如果该结点存在右孩子，则右孩子中存储的内容一定大于该结点存储的内容，如果同时存在左右孩子，那么结点中存储的内容一定满足左孩子<该结点<右孩子。

对于BST的详细内容在后面的篇章中我们会进一步介绍，目前大家只需要知道有这种特殊的二叉树即可。

2.4 平衡二叉树

定义：树上任意结点的左子树和右子树的深度之差不超过1。

平衡二叉树（Balanced Binary Tree）又称为AVL树。这是由Georgy Maximovich Adelson-Velsky和Evgenii Mikhailovich Landis两位大佬提出来的，因此就由这两位大佬的名字中的AV和L共同为该二叉树进行的命名。感兴趣的朋友可以点击AVL Trees来了解大佬们提出AVL Trees的事情经过。

下面我简单的说明一下什么事AVL树，如下图所示：