树

树是一种非线性的数据结构，它是由n个有限节点组成一个具有参次关系的集合。把它叫做树是因为逻辑结构是看起来像一颗倒挂的树。

树的特点

节点的度就是该节点的子节点个数：1节点的度是2，2节点的度是3
树唯一有个没有双亲节点的节点，该节点叫做根节点
树除了根节点外所有节点都当且仅有一个双亲节点
树中没有子节点的节点叫做叶节点
节点的层次是从根开始定义起，根为第1层，根的子节点为第2层，以此类推
树的深度是节点的最大层次，根节点的深度为1
兄弟节点就是具有相同双亲节点的节点

树的表示法

树不同于线性的表示，树的存储表示非常复杂，实际表示中也有很多表示方式：双亲表
示法，孩子表示法、孩子兄弟表示法等等

孩子兄弟表示法

孩子兄弟表示法的规则就是左孩子右兄弟，形象的说就是每个双亲节点带一个老大，后面的兄弟节点老二就由老大带，老三由老二带以此类推

typedef int DataType;
struct Node
{
	struct Node* pfirstChild;  //第一个孩子节点
	struct Node* pNextBrother; //指向其下一个兄弟节点
	DataType data; //存放数据
};

pfirstChild指向孩子节点，pNextBrother指向兄弟节点，当没有孩子或者兄弟节点就是NULL指针。通过这个存储方式就可以找到所有节点。

二叉树

二叉树就是树的每一个节点最多有2个孩子

满二叉树

满二叉树就是每层节点都是最大值，即如果一个二叉树有n层，如果节点数是2ⁿ-1那么这个树就是满二叉树

完全二叉树

完全二叉树就是除了最后一层其他层节点都是最大值，且倒数第二层从左到右依次存在孩子，注意满二叉树是一种特殊的完全二叉树

二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第n层上最多有2^n-1 个节点
若规定根节点的层数为1，则深度为n的二叉树的最大节点数是2ⁿ- 1
对任何一棵二叉树, 度为0的节点总比度为2的节点多1个。对于完全二叉树，度为1的节点树不是1就是0

顺序存储完全二叉树

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

链式存储二叉树

链式存储二叉树很容易理解因为跟逻辑结构几乎完全一致

堆

堆是一种特殊的完全二叉树，堆分为两种一个叫大根堆，另一个叫小根堆。大根堆是从根节点起所有的双亲节点大于等于其孩子节点，小根堆是从根节点起所有的双亲节点小于等于其孩子节点。
堆代码链接提取码：Heap

向下调整算法

向下调整算法是根节点下的左右子树都是小堆或者都是大堆的情况下的调整算法，目的是为了让该树变为堆。以两个子树都是小堆为例子：
从根节点起与两个孩子中最小的交换直到不能交换（1.比孩子都小 2.成为叶子），算法结束。由于左右子树都是小堆，所以无论跟谁交换不影响另一个小堆，由于未被交换的孩子一定大于被交换的孩子所以当被交换过的子树成为小堆整个树就可以成为小堆，依次进行直到不能交换时整树成为小堆。两个子树都是大堆的思路一致。

建堆

这里以建小堆为例，建堆其实就是反复的使用向下调整算法最终成为小堆

从下往上使用向下调整算法，因为在1中 9 和 11是小堆所以可以使用，在2中 34 和 21 是小堆所以可以使用，在3中 1 和 12 是小堆所以可以直接使用，在4中 3 和2是小堆可以直接使用，最后成为小堆。

这里建小堆是从最后一个叶子的双亲节点开始的，依次向前一个节点逐步使用向下调整算法，建大堆的方式与其相同。
向下调整算法与建堆代码链接
提取码：Heap

建堆时间复杂度O(n)分析

建堆的过程就是从最后一个双亲节点起到根节点对每个节点进行向下调整。向下调整的过程就是依次比较孩子与交换双亲与孩子，这个些执行的次数在最坏情况下就是层数，当是满二叉树时有n个节点时执行的次数就是log₂⁽ⁿ⁺¹⁾,因为满二叉树的层数x与节点数n的关系是 2^x-1 = n。所以向下调整的时间复杂度是O(logⁿ)。由于每个节点的执行向下调整的次数都不一样，所以要分别计算再求和。

堆排序

堆排序是利用堆的特性（大堆中根节点最大，小堆中根节点最小），依次来选出最大或者最小的数。这里以排升序为例子。方法是先建大堆，再将最后的节点数据与根节点交换，这样筛选出的最大数据放在最后，然后将筛选出的数据不算入堆中，此时就形成了根节点链接两个子树都是大堆，再向下调整找出最大数据，与最后数据交换，依次进行，这样就可以将最大数据依次放入最后从而形成升序。

堆排序代码链接
提取码：Sort