内容整理于鱼c工作室教程

1. 树的基本概念

1.1 树的定义

树(Tree)是n(n>=0)个结点的有限集。

当n=0时成为空树，在任意一棵非空树中：有且仅有一个特定的称为根(Root)的结点；

当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、…、Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。

虽然从概念上很容易理解树，但是有两点还是需要大家注意下：

n>0时，根结点是唯一的，坚决不可能存在多个根结点。

m>0时，子树的个数是没有限制的，但它们互相是一定不会相交的。

1.2 树的基本概念

(1) 结点：如上图，每一个圈圈我们就称为树的一个结点。

(2) 度: 结点拥有的子树数称为结点的度-(Degree)，树的度取树内各结点的度的最大值。

(3) 叶结点(Leaf)或终端结点: 度为0的结点。

(4) 内部结点: 度不为0的结点称为分支结点或非终端结点，除根结点外，分支结点也称为内部结点。

(5) 结点间的关系：结点的子树的根称为结点的孩子(Child)，相应的，该结点称为孩子的双亲(Parent)，同一双亲的孩子之间互称为兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。

(6) 深度：树中结点的最大层次称为树的深度(Depth)或高度。

(7) 结点的层次(Level): 从根开始定一起，根为第一层，根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。

(8) 有序树: 如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树, 否则为无序树。

(9) 森林(Forest): 是 m(m>=0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。

2. 树的存储结构

2.1 双亲表示法

双亲表示法，言外之意就是以双亲作为索引的关键词的一种存储方式。

我们假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示其双亲结点在数组中位置的元素。

也就是说，每个结点除了知道自己是谁之外，还知道它的粑粑妈妈在哪里。

这样的存储结构，我们可以根据某结点的parent指针找到它的双亲结点，所用的时间复杂度是O(1)，索引到parent的值为-1时，表示找到了树结点的根。

可是，如果我们要知道某结点的孩子是什么？那么不好意思，请遍历整个树结构。

当然可以，我们只需要稍微改变一下结构即可：

那现在我们又比较关心它们兄弟之间的关系呢？

2.2 孩子表示法

我们这次换个角度来考虑，由于树中每个结点可能有多棵子树，可以考虑用多重链表来实现。

就像我们虽然有计划生育，但我们还是无法确保每个家庭只养育一个孩子的冲动，那么对于子树的不确定性也是如此。

方法1: 根据树的度，声明足够空间存放子树指针的结点。

缺点十分明显，就是造成了浪费！

方法2:

这样我们就克服了浪费这个概念，我们从此走上了节俭的社会主义道路！但每个结点的度的值不同，初始化和维护起来难度巨大吧？

方法3:最佳解决方案。

那只找到孩子找不到双亲貌似还不够完善，那么我们合并上一讲的双亲孩子表示法：

3. 树的种类

3.1 二叉树

二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

3.1.1 二叉树的特点

(1) 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。（注意：不是都需要两棵子树，而是最多可以是两棵，没有子树或者有一棵子树也都是可以的。）

(2) 左子树和右子树是有顺序的，次序不能颠倒。

(3) 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树，下面是完全不同的二叉树：

3.1.2 二叉树的基本形态

从左到右，依次是(1) 空二叉树, (2)只有一个根结点, (3)根结点只有左子树, (4)根结点只有右子树

(5)根结点既有左子树又有右子树。

3.1.3 特殊二叉树

(1) 斜树

顾名思义，斜树是一定要斜的，但斜也要斜得有范儿，例如：

(2) 满二叉树

坡坡有云：“人有悲欢离合，月有阴晴圆缺，此事古难全。但愿人长久，千里共长娟。”意思就是说完美的那是理想，不完美的才是人生。

但是对于二叉树来说，是否存在完美呢？有滴，那就是满二叉树啦。

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

叶子只能出现在最下一层。

非叶子结点的度一定是2。

在同样深度的二叉树中，满二叉树的结点个数一定最多，同时叶子也是最多。

(3) 完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点位置完全相同，则这棵二叉树称为完全二叉树。

叶子结点只能出现在最下两层。

最下层的叶子一定集中在左部连续位置。

倒数第二层，若有叶子结点，一定都在右部连续位置。

如果结点度为1，则该结点只有左孩子。

同样结点树的二叉树，完全二叉树的深度最小。

注意：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

3.1.4 二叉树性质

(1) 在二叉树的第i层上至多有2^(i-1)个结点(i>=1)。

(2) 深度为k的二叉树至多有2^k-1个结点(k>=1)。

(3) 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

首先我们再假设度为1的结点数为n1，则二叉树T的结点总数n=n0+n1+n2

其次我们发现连接数总是等于总结点数n-1，并且等于n1+2*n2

所以n-1=n1+2*n2

所以n0+n1+n2-1=n1+n2+n2

最后n0=n2+1

(4) 具有n个结点的完全二叉树的深度为⌊log₂n⌋+1。

由满二叉树的定义结合性质二我们知道，深度为k的满二叉树的结点树n一定是2^k-1

那么对于满二叉树我们可以通过n=2^k-1倒推得到满二叉树的深度为k=log₂(n+1)

由于完全二叉树前边我们已经提到，它的叶子结点只会出现在最下面的两层，我们可以同样如下推导

那么对于倒数第二层的满二叉树我们同样很容易回推出它的结点数为n=2^(k-1)-1

所以完全二叉树的结点数的取值范围是：2^(k-1)-1 < n <= 2^k-1

由于n是整数，n <= 2^k-1可以看成n < 2^k

同理2^(k-1)-1 < n可以看成2^(k-1) <= n

所以2^(k-1) <= n < 2^k

不等式两边同时取对数，得到k-1<=log₂n

由于k是深度，必须取整，所以k=⌊log₂n⌋+1

(5) 如果对一棵有n个结点的完全二叉树(其深度为⌊log₂n⌋+1)的结点按层序编号，对任一结点i(1<=i<=n)有以下性质：

如果i = 1，则结点 i 是二叉树的根，无双亲；如果i > 1，则其双亲是结点⌊i/2⌋

如果2i > n，则结点 i 无做左孩子(结点 i 为叶子结点)；否则其左孩子是结点2i

如果2i+1 > n，则结点 i 无右孩子；否则其右孩子是结点2i+1

3.1.4 二叉树的存储

在前边的演示中，我们发觉很难单单只用顺序存储结构或者链式存储结构来存放。

但是二叉树是一种特殊的树，由于它的特殊性，使得用顺序存储结构或链式存储结构都能够简单实现。

(1) 顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的各个结点，并且结点的存储位置能体现结点之间的逻辑关系。

这下看出完全二叉树的优越性来了吧？由于他的严格定义，在数组直接能表现出逻辑结构。

当然对于一般的二叉树，尽管层序编号不能反映逻辑关系，但是也可以按照完全二叉树编号方式修改一下，把不存在的结点用“^”代替即可。

但是考虑到一种极端的情况，回顾一下斜树，如果是一个又斜树，那么会变成什么样？

(2) 链式存储结构

既然顺序存储方式的适用性不强，那么我们就要考虑链式存储结构啦。二叉树的存储按照国际惯例来说一般也是采用链式存储结构的。

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

3.1.5 二叉树的遍历

二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

二叉树的遍历方式可以很多，如果我们限制了从左到右的习惯方式，那么主要就分为一下四种：

(1) 前序遍历

若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。

遍历的顺序为：ABDHIEJCFKG

(2) 中序遍历

若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。

遍历的顺序为：HDIBEJAFKCG

注意！是先F再K,因为是先遍历结点的左子树然后结点然后右子树。因为没有左子树，所以直接结点再右子树。

(3) 后序遍历

若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。

遍历的顺序为：HIDJEBKFGCA

(4) 层序遍历

若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

遍历的顺序为：ABCDEFGHIJK

3.2 线索二叉树

我想正如程序猿发觉单链表并不总能满足他们设计的程序某些要求的时候，发明了双向链表来弥补一样，线索二叉树也是在需求中被创造的！那普通的二叉树到底有什么缺陷让我们发指呢？

10个！

没错，中序遍历可以拯救地球！

上图经过中序遍历后结果是：HDIBEAFCG

我们发现红色的结点都是刚才“^”造成浪费的结点，利用中序遍历刚好它们均处于字符中间，可以很好地利用“^”来存放前驱和后继的指针。不过好事总是多磨的，我们是有主观意识所以可以很容易出来哪些结点可以利用存放前驱后继。这所谓的主观意识还不简单，不就是从第一个开始每隔一个结点都可以？

上图经过中序遍历后结果是：FDGBACE

黄色说明只有一个空闲的指针位置，如果是这样的话我们就面临一个问题：机器怎么识别到底是存放指针还是线索？

没错，她需要一丁点儿提示，为此我们将已经定义好的结构进行“扩容”：

3.3 查找二叉树

二叉查找树就是二叉排序树，也叫二叉搜索树。二叉查找树或者是一棵空树，或者是具有下列性质的二叉树： (1) 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；(2) 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；(3) 左、右子树也分别为二叉排序树；(4) 没有键值相等的结点。

对于二叉查找树来说，当给定值相同但顺序不同时，所构建的二叉查找树形态是不同的，下面看一个例子。

可以看到，含有n个节点的二叉查找树的平均查找长度和树的形态有关。最坏情况下，当先后插入的关键字有序时，构成的二叉查找树蜕变为单支树，树的深度为n，其平均查找长度(n+1)/2(和顺序查找相同），最好的情况是二叉查找树的形态和折半查找的判定树相同，其平均查找长度和log2(n)成正比。平均情况下，二叉查找树的平均查找长度和logn是等数量级的，所以为了获得更好的性能，通常在二叉查找树的构建过程需要进行“平衡化处理”，之后我们将介绍平衡二叉树和红黑树，这些均可以使查找树的高度为O(log(n))。

3.4 平衡二叉树

平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。

AVL树是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为1，所以它也被称为高度平衡树，n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

3.5 红黑树

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性:

（1）每个节点或者是黑色，或者是红色。

（2）根节点是黑色。

（3）每个叶子节点（NIL）是黑色。[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]

（4）如果一个节点是红色的，则它的子节点必须是黑色的。

（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

注意：

(01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。

(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

3.5.1 左旋与右旋

红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。

(1) 左旋

更复杂的例子：

(2) 右旋

更复杂的例子：