二叉树简介

文章目录

• 1.基本概念
• 2.五种形态
• 3.特殊二叉树
• 4.基本性质
• 5.存储结构
• 6.拓展阅读
• 参考文献

二叉树是一类简单而又重要的树形结构，在数据的排序、查找和遍历方面有着广泛的应用。由于其清晰的结构，简单的逻辑，广泛的应用和大量的指针操作，在面试过程屡见不鲜，快被面试官玩坏了。相关的问题在百行代码内就可解决，特别适合手写代码，因此我们要充分做好准备，迎接面试时关于二叉树的相关问题，尤其是手写代码。

1.基本概念

了解二叉树的基本概念是掌握二叉树的第一步，下面简单介绍一下二叉树的常见的概念。

树结点：包含一个数据元素及若干指向子树的指针元素； 根结点：没有父结点的结点； 父结点：除了根结点，每个结点都有一个直连的前置结点，后者是前者的父结点； 子结点：除了叶子结点，每个结点都有一个直连的后置结点，后者是前者的子结点； 叶子结点：无子结点的结点； 分支结点：除叶子结点外的结点，即度不为 0 的结点； 兄弟节点：拥有相同父结点的结点； 祖先节点：从根到该结点的所经分支上的所有结点； 子孙节点：以某结点为根的子树中任一结点都称为该结点的子孙； 树高度：树的结点层数。根结点为第一层，根的子结点为第二层，以此类推； 结点的度：子结点的个数； 树的度： 树中最大的结点度； 左子树：左子结点为根形成的二叉树； 右子树：右子结点为根形成的二叉树； 路径：从一个结点往下到达子孙结点之间的通路，称为路径； 路径长度：路径中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第 L 层结点的路径长度为 L-1； 森林：由 m（m>=0）棵互不相交的树组成的集合称为森林。

2.五种形态

二叉树可以定义为节点的有限集合，或者为空集，或者为根节点及其左右子树的节点集合。因此二叉树具有五种基本形态。 （1）空二叉树。

在这里插入图片描述

（2）只有一个根节点。

这里写图片描述

（3）有根节点和非空左子树。

在这里插入图片描述

（4）有根节点和非空右子树。

在这里插入图片描述

（5）有根节点并且左右子树均为非空。

这里写图片描述

3.特殊二叉树

二叉树有两大类，一是普通二叉树，二是特殊二叉树。除了特殊二叉树，都是普通二叉树。普通二叉树不用多说，重点说一下特殊二叉树。

• 斜树

所有结点只有左子树的二叉树叫左斜树。所有结点只有右子树的二叉树叫右斜树。两者统称为斜树。

在这里插入图片描述

• 完全二叉树

若设二叉树的高度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

一维数组可以作为完全二叉树的存储结构，堆排序使用的数据结构就是完全二叉树。如下图所示：

这里写图片描述

• 满二叉树

国际标准定义是每个结点都有 0 或 2 个子结点的二叉树。如下图所示：

这里写图片描述

注意： 这里的定义与国内教材的定义不同，国内的定义是：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。很显然，按照这个定义，上面图示的二叉树不是满二叉树。

• 扩充二叉树

在二叉树中出现空的子树（包括树叶）上增加空的树叶，使其成为满二叉树（国际定义）的二叉树称之为扩充二叉树。

扩充二叉树是对已有二叉树的扩充，扩充后的二叉树的结点都变为度数为 2 的分支节点。也就是说，如果原节点的度数为 2，则不变，度数为 1，则增加一个空的叶子结点，度数为 0 的叶子节点则增加两个空的叶子结点。

如下如所示，一棵普通二叉树及其扩充二叉树：

这里写图片描述

• 平衡二叉树

一棵空树或它的任意结点的左右两个子树的高度差的绝对值不超过 1。

这里写图片描述

• 二叉搜索树

是一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； （3）左、右子树也分别为二叉搜索树；

在这里插入图片描述

• 哈夫曼树

给定 N 个权值作为 N 个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为哈夫曼树(Huffman Tree)，也称为最优二叉树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

哈夫曼树是二叉树的一种特殊形式，其主要作用在于数据压缩和编码长度的优化。

在这里插入图片描述

假设上面的哈夫曼树用于编码，编码规则采用从根节点出发，向左标记为 0，向右标记为 1，编码结果为：

在编码长度较长，且权值分布不均匀时，采用哈夫曼编码可以大大缩短编码长度。

此外，还有一些重要的特殊二叉树，比如线索二叉树和红黑树等，这里不再赘述，感兴趣的同学可自行查阅相关资料。另外常用于数据库索引的多叉树如 B 树 和 B+ 树也建议了解一下。

4.基本性质

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

（2）若规定只有根节点的二叉树的高度为 1，则高度为 h 的二叉树最少有 h 个结点，最多有 2^h-1 结点；

（3）如果其叶结点数为 n0，而度数为 2 的结点总数为 n2，则 n0=n2+1；

（4）具有 n 个结点的完全二叉树的深度为

；

（5）有 n 个结点的完全二叉树各结点如果用顺序方式存储，从上至下从左至右的顺序对所有结点从 0 开始编号，则对于编号为 i 的节点有： （a）若 i > 0，则其父结点的编号为 (i-1)/2； （b）左孩子编号为 2i+1。若 2i+1>n-1，则无左孩子； （c）左孩子编号为 2i+2。则 2i+1>n-1，则无右孩子。

（6）给定 n 个结点，能构成 h(n) 种不同的二叉树。h(n) 为卡特兰数的第 n 项。h(n)=C(2n,n)/(n+1)。

对于以上二叉树基本性质的理解，可以参考下面的完全二叉树来帮助理解。

在这里插入图片描述

5.存储结构

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

• 顺序存储

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

在这里插入图片描述

其中，∧表示数组中此位置没有存储结点。此时可以发现，顺序存储结构中已经出现了空间浪费的情况。如果出现斜树这种极端情况，采用顺序存储的方式是十分浪费空间的。因此，顺序存储一般适用于完全二叉树。

• 链式存储

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

在这里插入图片描述