1、树的概念及结构

1.1：树的概念：

树是一种非线性的数据结构，由n（n>=0)个有限的结点组成一个具有层次关系的集合。

PS：①为什么n可以等于0？因为空结点的空树也是树。②树结构中，子树之间是不能由交集的！

O7KAWKT6R@19ZAGT1JASH%T.png ${E2IXM}S[K0%NI_{$B%ESK4.png$

1.2：树的相关概念：

※节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6
※叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I...等节点为叶节点

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

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

※孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点
※兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点

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

※节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
※树的高度或深度：树中节点的最大层次；如上图：树的高度为4

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

※节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先
※子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙
※森林：由m（m>0）棵互不相交的树的集合称为森林；

1.3 树的表示

由于树结构相对于线性表来说比较复杂，既要存储值域，也要存储节点与节点之间的关系，因此，在很多相关的书籍上都有介绍树的表示方法，比如说在我的大学教材上就有：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。在这里就简单的介绍其中最常用的孩子兄弟表示法。

所谓孩子兄弟表示法，通常我把其记为：左孩子右兄弟。

B2{J58VX%5`{7[I(F(Q[]IN.png

对于每一层的根节点，我只需要记住右孩子，然后通过右孩子来找到其他的孩子。这里的左图为逻辑结构，是我们想象出来的，右图是物理结构，也称为存储结构，是实际上的结构。因此，通过这个方式来表示树。以下是树的代码的简单展示：

$I{33(61ULQ@8_3SSYO$AQ[4.png$

1.4 树在实际中的运用

在Linux系统中，表示文件系统的目录树结构。

`1GVO({)Y78238~~$F)JU6G.png

2.二叉树的概念及结构

2.1 概念

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

1. 或者为空

2. 由一个根节点加上两棵被称为左子树和右子树的二叉树组成

由图可知：①二叉树不存在大于2的度 ②二叉树的子树有左右之分，不能颠倒顺序，因此二叉树是有序树

H(}F$I{2`OU@VMA{C{AFTZQ.png

其实，对于每一棵二叉树，都是由空树、只有根节点的树、只有左子树、只有右子树和左右子树均存在的树复合而成。

2ZM$F)VHX6(OJ_UF$[ERVSF.png

2.2 现实中的二叉树

`6ON]@S(0S$[1Y4B$Y`0)_R.png

有句话说得好：区分程序员与非程序员的方法之一，就是看到这上面的树后，脑袋里第一想到的是什么？if(想到的是二叉树) 那你是程序员了； else if (想到的是：哇，这里的风景好独特好美）那你就是非程序员了；

2.3 特殊的二叉树

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

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

`U%J~SLKPGKEL9QNNX1A$L3.png

对于完全二叉树：前k-1层都是满的，最后一层可以是满，也可以不满，但是要求从左到右是连续的，否则就不是完全二叉树了，其节点范围 [ 2^(k-1) , 2^k-1 ]。

2.4 二叉树的性质

① 若规定根节点的层数为1(从1开始，不是按数组的下标形式），则一棵非空二叉树的第i层上最多有2^(i-1)个结点：也就是最多最多就是满二叉树的形式。

② 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1：也就是满二叉树的形式

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

④ 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= log(n+1).(ps:long(n+1)是log以2

为底，n+1为对数)

⑤ 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

·若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

· 若2i+1左孩子序号：2i+1，2i+1>=n则无左孩子

· 若2i+2右孩子序号：2i+2，2i+2>=n则无右孩子

2.5 二叉树的存储结构

二叉树的存储结构一般分为顺序结构和链式结构

①顺序存储

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

②链式存储

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

3·二叉树顺序结构及实现

3.1二叉树的顺序结构：

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

3.2 堆的概念及结构

如果由一组数据->K = {k0,k1,k2,k3,k4.....},把他们按照二叉树的顺序存储方式存储在一个一维数组中，并满足Ki<=K(i*2+1) && Ki<=K(i*2+2) (小根堆）或者是Ki>=K(i*2+1) && Ki>=K(i*2+2) （大根堆） i = 0,1,2,3.....。简单来说，如下图：

对于小根堆，根节点小于等于两个孩子节点。对于大根堆，根节点大于等于两个孩子节点！

公式：LeftChild = Parent*2+1（奇数）; RightChild = parent*2+2（偶数）; Parent = (LeftChild-1)/2;

一般来说，我们在运用的时候，需要使用孩子节点来计算父母节点的时候，一般都只需要使用Parent = (LeftChild-1)/2;

为什么？因为无论是Parent = (LeftChild-1)/2; 还是Parent = (RightChild-2)/2,计算出来的结果都是一样的(对于程序员的计算），因此我们可以把公式化为：Parent = (child-1)/2;

M3VMF`0)7E[WF{UZUJW036L.png

3.3 堆的实现

实现思路：通过根节点开始，向下调整算法可以把它调整成一个小根堆。注意：左右子树必须是一个堆才能调整。

OL(E9Q(V0}FQ0H4AH@C3XXU.png

下面，我们开始实现堆。

3.3.1 堆的创建：

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

int a[] = {1,5,3,8,7,6}

T7DUJCH2)()%EGP`FC`HS3E.png

3.3.2 堆的时间复杂度（向下调整算法）：因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明，由此证明：堆的时间复杂度为O(N);

IVGDC(@FXM$1W%%F$~V$TYH.png

3.3.3 堆的代码实现：这里展示最重要的部分，完整代码在：堆的实现: 堆的基本操作

※堆的插入：先将要插入的数据插入到堆尾，然后进行向上调整算法，直到满足堆。向上调整：将插入的数据X(child)，跟其父母节点(paren)的值Y对比：

若要实现小根堆，则：若X>=Y，就不用调整，直接满足堆。若X

D8`E(8G1QTPNIDEA~E)1OSC.png

※堆的删除：一般删除堆的元素，都是删除堆的顶点元素，这跟堆的作用有关：堆是一般用来求一大堆数据中的值比较大的或值比较小的数据，因此直接从顶点上取得元素。所以，删除元素的思路是：把要删除的元素（顶点元素）跟堆尾的元素交换，然后删掉堆尾的元素。接着，要向下调整：跟顶点元素跟它的孩子节点（child）对比，这里是思路跟插入的思路类似。这个顶点元素为X（parent），要找到最小孩子的节点Y（minchild）。于是，若X<=Y,那么满足小根堆，不需要调整了。否则，需要交换X和Y的值，然后将parent = minchild，接着更新minchild的位置，也就是往下对比。这里需要注意的是：在找孩子节点的时候，有可能只存在一个孩子节点，那么就可能会出现溢出的问题，因此在找孩子节点是时候，需要判断孩子节点是否存在。代码如下：

$%X}8GD6{_VST8GI_HP]74Q2.png$

3.4 堆的应用

①堆排序：即利用堆的思想来进行排序。

要进行堆排序，要进行两步：第一步是创建堆；第二步是进行排序

▶ 创建堆，创建堆的方法有向上调整算法和向下调整算法两种。首先我们来比较以下，这两种方法的时间复杂度：

上面我们以及算出向下调整算法的时间复杂度为O(N）。对于向下调整而言，它有个条件需要符合，才能进行，那就是它调整的时候，它的左右子树均为堆，而是是相同的堆。因此，我们其实是可以从倒数第二层开始调整，而不需要从最后一层开始的，因为最后一层是叶子节点，是已经符合堆的要求，因此，我们可以跳过最后一层，直接从倒数第二层开始。这样就可以提高效率。

对于向上调整，它就需要整棵树完全调整，越往根节点，调整次数最多，效率也就比向下调整算法低。向上调整的时间复杂度：

${W_O)UDY]BFRP)JE{C90DPN.png$

这跟向下调整类似，然后我们直接计算最后一层，就发现，其实际复杂度就是为O(N*logN)

BLGJ$1T4Y{`UJ]I0]EJQJ9J.png

因此，若要提高建堆的效率，建议选择使用向下调整算法。

$R{3[7UICL}T@DO%TLLUK_O0.png$

▶选数：即要排序成升序还是降序

首先要分析出，要排序，是用大根堆还是小根堆？其实很简单，这里使用升序作为例子：若选择小根堆，那么，堆顶的数必然是最小的，因此要将堆顶的数删掉，出堆！但是！删掉堆顶的元素后，堆的结构就会被破坏掉，需要重新建堆！建堆的时间复杂度是O(N)，每次取堆顶元素都要重新建堆，效率可想而知，是不高效的！

}{6Q@4~XC@DOE9U@DCRQS4G.png

而若是使用大根堆，堆尾的元素是最小的，便可以将堆顶的元素和堆尾的元素交换，然后重新向下调整，每一次调整可以除去交换后的堆尾元素，直到排序成功。

因此，要升序，我们选择使用大根堆，思路为：①建大堆 ②第一个和最后一个的位置交换，把最后一个不看做堆里面的数据，然后向下调整，选出依次最大的。后续依次类似处理。

40%}K5{@{BY8U1[}Q[N%NE9.png

反之，要降序，我们可以使用小根堆，思路和操作与升序基本相同。

例子：给出数组，然后进行堆排序，要升序。代码如下：

int a[] = { 15, 1, 19, 25, 8, 34, 65, 4, 27, 7 };

3QO8HAONG3L~1{}W}Z5`S[V.png

5B4K4J)}84`71C}[NY)6DTM.png

%Y}5DTN%MKM%HI~XKPD193L.png

②TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。前面的删除操作，也提到了这一点。

既然要在很大的一堆数据中选出前K个最大或最小的元素，我们也要分析一下，是用大根堆还是小根堆？

这里用选出前K个最大的元素，进行分析：

我们要在一百万个数据中，选出K个最大的数，如果选择大根堆，那么，我们就必须在这一百万个数据中，找到其中的K个最大的数据。在那么多个数中选那么少的数，要是内存放不下，就得弄到磁盘中去放。如果有人说一百万个数，内存能装下，那么一千万个呢？一亿个呢？

如果选择小根堆，我们只需在这一百万个数里面，将前K个数创建出小根堆，然后用剩下的一百万-K个数与堆顶的数进行比较，谁大，就将谁替换到堆顶，然后进行向下调整。最后，堆里面的就是一百万个数据里面的最大的K个数了。

类似的，要选出K个最小的数，那就使用大根堆。

代码如下：

CI88J5ZZ%4NW7QDJ03E}E(9.png

在测试用例里，生产的随机数都是小于一百万的，因此我在这些数里面，再加入一百万及以上的数，进行测试：结果如下：

6`96[SR5%7902PGA63C1{P7.png

4.二叉树的链式结构及实现

4.1 二叉树的代码实现

二叉树的遍历有前序/中序/后序/层序

3X3FTO86NFV4YWRLHRA6J~Q.png

▶前序遍历，又称先序遍历：遍历的顺序为根->左子树->右子树。

8@ZHTABYMN38KZU3BZ7JQD1.png

我们可以通过代码来分析一下遍历的过程：首先是进入函数，第一个根节点不为空，就先从左子树开始遍历，左子树遍历完就到右子树，通过每一次的递归调用。这里需要注意的是，当左子树遍历完后，递归时创建的栈帧已经被销毁了，而当右子树开始递归，创建函数栈帧的时候，用的可能就是已经被销毁的左子树的函数栈帧，因此，空间效率没有想象中的那么低，空间是可以重复利用的！

$_6)L%AYBFO]H6I{E118RKYO.png$