二叉树
1.树概念及结构
1.1树的概念
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下。
- 有一个特殊的结点，称为根结点，根结点没有前驱结点。
- 除根结点外，其余结点被分成M(M>0)互不相交的集合T1,T2…Tm，其中每一个集合Ti(1<=i<=m)又是一颗结构与树类似的子树，每棵子树的根结点有且仅有一个前驱，可以有0个或多个后继。因此，树是递归定义的。
注意：树形结构中，子树之间不能有交集，否则就不是树形结构
1.2 树的相关概念
- 结点的度：一个结点含有的子树的个数称为该结点的度。
- 叶结点（终端结点）：度为0的结点称为叶结点。
- 非终端结点（分支结点）：度不为0的结点。
- 父结点（双亲结点）：若一个结点含有子结点，则这个结点称为其子结点的父结点。
- 子结点（孩子结点）：一个结点含有的子树的根结点称为该结点的子结点。
- 兄弟结点：具有相同父结点的结点互称为兄弟结点。
- 树的度：一棵树中，最大的结点的度称为树的度。
- 结点的层次：从根开始定义起，根为第一层，根的子结点为第二层，以此类推。
- 树的高度（树的深度）：树中结点的最大层次。
- 堂兄弟结点：双亲在同一层的结点互称为堂兄弟结点。
- 结点的祖先：从根到该结点所经分支上的所有结点。
- 子孙：以某结点为根的子树中任一结点都称为该结点的子孙。
- 森林：由m(m>0)棵互不相交的树组成的集合称为森林。
1.3 树的表示
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
我们这里就简单的了解其中最常用的孩子兄弟表示法：
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};
对于任意树，我们都可以用孩子兄弟法访问到树中的每一个结点：
贴士： 树在实际中的运用：表示文件系统的目录树结构
2.二叉树概念及结构性质
2.1概念
二叉树是n个结点的有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。
二叉树的特点： 每个结点最多有两个棵子树，即二叉树不存在度大于2的结点。 二叉树的子树有左右之分，其子树的次序不能颠倒。
注意：对于任意的二叉树都是由以下几种情况复合而成的
2.2特殊的二叉树
-
满二叉树：一个二叉树，如果每一层的结点数都达到最大值，则这个二叉树就是满二叉树。从形象来看的话满二叉树是一个绝对的三角形，最后一层全部是叶子节点，其它各层是非叶子节点，节点数的计算n=2^k - 1,k表示深度，也就是层数，第i层的节点数n= 2^(i- 1),它的节点数是一系列固定的数，如果节点数不是序列中的数的话，就不是满二叉树。
-
完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。完全二叉树的节点数是任意的，从形式上讲它是个缺失的的三角形，但所缺失的部分一定是右下角某个连续的部分,若数的深度为K，那么它的前K-1层的结点数必须都是满的，第K层的结点数可以不是满的但是从左到右必须是连续的，对于k层的完全二叉树，节点数的范围
2^ (k - 1) -1 < N< 2^k - 1;要注意的是满二叉树是一种特殊的完全二叉树。
2.3二叉树的性质（重要！！！）
- 性质一：若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有
2^(i-1)个结点。 - 性质二：若规定根结点的层数为1，则深度为h的二叉树的最大结点数为
2^h-1个。 - 性质三：对任何一棵二叉树，如果度为0的叶结点个数为n0，度为2的分支结点个数为n2，则有
n0 = n2+1。 - 性质四：若规定根结点的层数为1，则具有N个结点的满二叉树的深度h =
log2(N+1)。
习题：
1.某二叉树共有399个结点，其中199个度为2的结点，则该二叉树中的叶子结点数为（ ）。
A.不存在这样的二叉树
B.200
C.198
D.199
1.（答案：B）根据性质三，叶子结点（度为0）的个数200个，由于199+200 = 399（该二叉树的总结点数），所以该二叉树的叶子结点数为200。
2.在具有2n个结点的完全二叉树中叶子结点个数为（ ）。
A.n
B.n+1
C.n-1
D.n/2
2.（答案：A）根据性质三，度为0的结点数和度为2的结点数之和应为奇数，因为该完全二叉树的结点总数为2n（偶数），所以二叉树中必然存在一个度为1的结点。于是可以推出：度为0的结点和度为2的结点总共有2n-1个。性质三：对任何一棵二叉树，度为0的叶结点个数比度为2的分支结点个数多1，所以该二叉树度为2的结点个数为n-1，度为0的结点数（即叶结点数）为n。
注意理解：任何一棵完全二叉树中度为1的结点要么有1个，要么就没有度为1的结点。因为完全二叉树的最后一层的结点必须是从左到右连续的，而位于最后一层之前的层数的结点的度均为2。
3.一棵完全二叉树的结点数为531，那么这棵树的高度为（ ）。
A.11
B.10
C.8
D.12
3.（答案：B）假设该完全二叉树的层数为K，则该完全二叉树的前K-1层的结点总数为2^(K-1)-1，若该完全二叉树是满二叉树，则该满二叉树的结点总数为2 ^K-1，所以深度为K的完全二叉树的结点总数范围为：2 ^ (K-1)-1< N <= 2 ^K-1。因为2 ^9 < 531 <= 2 ^10，所以该完全二叉树的高度为10。
4.一个具有767个结点的完全二叉树，其叶子结点个数为（ ）。
A.383
B.384
C.385
D.386
4.（答案：B）该题与第2题的道理是一样的，因为度为0的结点数和度为2的结点数之和应为奇数，又因为该完全二叉树的结点总数为767（奇数），所以二叉树中必然不存在一个度为1的结点，因此度为2的结点个数为383，度为0的结点个数为384，即叶子结点个数为384。
2.4 二叉树的存储结构
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
- 顺序存储
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。
2.链式结构
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素之间的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来存储该结点左孩子和右孩子所在的结点的地址。
链式结构又分为二叉链和三叉链，之后我们会用二叉链来实现二叉树的链式存储结构，三叉链运用于更高阶的数据结构，例如红黑树。三叉链相比二叉链多了一个指向双亲节点的指针。
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pParent; // 指向当前节点的双亲
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}；
3.二叉树的顺序结构及实现
普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储。
注意：这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
3.1 堆的概念及结构
堆的概念
堆：如果有一个关键码的集合K={k0,k1,k2,…,kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足ki<=k2i+1且ki<=k2i+2（或满足ki>=k2i+1且ki>=k2i+2），其中i=0,1,2,…，则称该集合为堆。
堆的性质：
- 堆中某个结点的值总是不大于或不小于其父结点的值。
- 堆总是一棵完全二叉树。
- 堆中每个结点的子树都是堆树。
小堆：将根结点最小的堆叫做小堆，也叫最小堆或小根堆。
大堆：将根结点最大的堆叫做大堆，也叫最大堆或大根堆。
3.2 堆的实现
3.2.1 堆向下调整算法（时间复杂度为：O(logN)）
现在我们给出一个数组
int array[] = {27,15,19,18,28,34,65,49,25,37};
逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
本二叉树以27为根的左右子树都满足小堆，只有根节点不满足，因此只需要将根节点往下调整，整到合适的位置即可形成小堆。
向下调整算法的基本思想（以建小堆为例）：
1.从根结点处开始，选出左右孩子中值较小的孩子。
2.让小的孩子与其父亲进行比较：
- 若小的孩子比父亲还小，则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
- 若小的孩子比父亲大，则不需处理了，调整完成，整个树已经是小堆了。
代码实现：
//交换函数
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//堆的向下调整（小堆）
void AdjustDown(int* a, int n, int parent)
{
//child记录左右孩子中值较小的孩子的下标
int child = 2 * parent + 1;//先默认其左孩子的值较小
while (child < n)
{
if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小
{
child++;//较小的孩子改为右孩子
}
if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小
{
//将父结点与较小的子结点交换
Swap(&a[child], &a[parent]);
//继续向下进行调整
parent = child;
child = 2 * parent + 1;
}
else//成堆
{
break;
}
}
}
使用堆的向下调整算法，最坏的情况下（即一直需要交换结点），需要循环的次数为：h - 1次（h为树的高度）。而h = log2(N+1)（N为树的总结点数）。所以堆的向下调整算法的时间复杂度为：O(logN) 。
3.2.2堆的创建（时间复杂度=T ( n ) = O ( N ) ）
向下调整法建堆
下面我们再给出一个数组：
int array[] = {23，54，76，33，89，12，78，34，87，10};
这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行，那么如何才能将一个任意树调整为堆呢？现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，从后往前，按下标，依次作为根去向下调整一直调整到根节点的树，就可以调整成堆。
代码实现：
//建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(php->a, php->size, i);
}
向上调整法建堆
给定n个数的数组a,用向上调整法建堆
for(int i=0;i<n;++i)
{
adjustup(a,i);//堆的向上调整（从第i个位置开始，每插入一个数，把当前所有数当作一个堆）
}
3.2.3建堆的时间复杂度
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
向上和向下调整建堆的时间复杂度都是O（N）
3.2.4 堆的插入(向上调整算法)
先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。
代码实现：
//交换函数
void Swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
//堆的向上调整（小堆）
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)//调整到根结点的位置截止
{
if (a[child] < a[parent])//孩子结点的值小于父结点的值
{
//将父结点与孩子结点交换
Swap(&a[child], &a[parent]);
//继续向上进行调整
child = parent;
parent = (child - 1) / 2;
}
else//已成堆
{
break;
}
}
}
接下来我们对堆进行比较全面的实现
3.2.5堆的实现
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}Hp;
// 堆的构建
void HeapInit(Hp* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Hp* hp);
// 堆的插入
void HeapPush(Hp* hp, HPDataType x);
// 堆的删除
void HeapPop(Hp* hp);
// 取堆顶的数据
HPDataType HeapTop(Hp* hp);
// 堆的数据个数
int HeapSize(Hp* hp);
// 堆的判空
int HeapEmpty(Hp* hp);
初始化堆
首先，必须创建一个堆类型，该类型中需包含堆的基本信息：存储数据的数组、堆中元素的个数以及当前堆的最大容量。
typedef int HPDataType;//堆中存储数据的类型
typedef struct Heap
{
HPDataType* a;//用于存储数据的数组
int size;//记录堆中已有元素个数
int capacity;//记录堆的容量
}HP;
然后我们需要一个初始化函数，对刚创建的堆进行初始化，并将传入数据实现建堆操作。
//初始化堆
void HeapInit(HP* php, HPDataType* a, int n)
{
assert(php);
HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType)*n);//申请一个堆结构
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
php->a = tmp;
memcpy(php->a, a, sizeof(HPDataType)*n);//拷贝数据到堆中--memcpy满足任意类型的拷贝（因为接收f的是void*）
php->size = n;
php->capacity = n;
int i = 0;
//建堆
for (i = (php->size - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(php->a, php->size, i);
}
}
销毁堆
为了避免内存泄漏，使用完动态开辟的内存空间后都要及时释放该空间，所以，一个用于释放内存空间的函数是必不可少的。
//销毁堆
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);//释放动态开辟的数组
php->a = NULL;//及时置空
php->size = 0;//元素个数置0
php->capacity = 0;//容量置0
}
打印堆
打印堆中的数据，这里用了两种打印格式。第一种打印格式是按照堆的物理结构进行打印，即打印为一排连续的数字。第二种打印格式是按照堆的逻辑结构进行打印，即打印成树形结构。
//求结点数为n的二叉树的深度
int depth(int n)
{
assert(n >= 0);
if (n>0)
{
int m = 2;
int hight = 1;
while (m < n + 1)
{
m *= 2;
hight++;
}
return hight;
}
else
{
return 0;
}
}
//打印堆
void HeapPrint(HP* php)
{
assert(php);
//按照物理结构进行打印
int i = 0;
for (i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
printf("\n");
//按照树形结构进行打印
int h = depth(php->size);
int N = (int)pow(2, h) - 1;//与该二叉树深度相同的满二叉树的结点总数
int space = N - 1;//记录每一行前面的空格数
int row = 1;//当前打印的行数
int pos = 0;//待打印数据的下标
while (1)
{
//打印前面的空格
int i = 0;
for (i = 0; i < space; i++)
{
printf(" ");
}
//打印数据和间距
int count = (int)pow(2, row - 1);//每一行的数字个数
while (count--)//打印一行
{
printf("%02d", php->a[pos++]);//打印数据
if (pos >= php->size)//数据打印完毕
{
printf("\n");
return;
}
int distance = (space + 1) * 2;//两个数之间的空格数
while (distance--)//打印两个数之间的空格
{
printf(" ");
}
}
printf("\n");
row++;
space = space / 2 - 1;
}
}
堆的插入
数据插入时是插入到数组的末尾，即树形结构的最后一层的最后一个结点，所以插入数据后我们需要运用堆的向上调整算法对堆进行调整，使其在插入数据后仍然保持堆的结构。
//堆的插入
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
HPDataType* tmp = (HPDataType*)realloc(php->a, 2 * php->capacity*sizeof(HPDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
php->a = tmp;
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
//向上调整
AdjustUp(php->a, php->size - 1);
}
堆的删除
堆的删除，删除的是堆顶的元素，但是这个删除过程可并不是直接删除堆顶的数据，而是先将堆顶的数据与最后一个结点的位置交换，然后再删除最后一个结点，再对堆进行一次向下调整。
原因：我们若是直接删除堆顶的数据，那么原堆后面数据的父子关系就全部打乱了，需要全体重新建堆，时间复杂度为 O ( N ) 。若是用上述方法，那么只需要对堆进行一次向下调整即可，因为此时根结点的左右子树都是小堆，我们只需要在根结点处进行一次向下调整即可，时间复杂度为 O ( log ( N ) ) 。
//堆的删除
void HeapPop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
Swap(&php->a[0], &php->a[php->size - 1]);//交换堆顶和最后一个结点的位置
php->size--;//删除最后一个结点（也就是删除原来堆顶的元素）
AdjustDown(php->a, php->size, 0);//向下调整
}
获取堆顶的数据
获取堆顶的数据，即返回数组下标为0的数据。
//获取堆顶的数据
HPDataType HeapTop(HP* php)
{
assert(php);
assert(!HeapEmpty(php));
return php->a[0];//返回堆顶数据
}
获取堆的数据个数
获取堆的数据个数，即返回堆结构体中的size变量。
//获取堆中数据个数
int HeapSize(HP* php)
{
assert(php);
return php->size;//返回堆中数据个数
}
堆的判空
堆的判空，即判断堆结构体中的size变量是否为0。
//堆的判空
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;//判断堆中数据是否为0
}
3.3 堆的应用
3.3.1 堆排序
堆排序即利用堆的思想来进行排序，总共分为两个步骤：
- 建堆
- 排升序：建大堆
- 排降序：建小堆
- 利用堆删除思想来进行排序
建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
以排升序（建大堆）为例：
1.先利用向下调整法建堆：
//建堆（大堆）
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(php->a, php->size, i);
}
2.再利用堆删除思想来进行排序：
步骤如下：
1、将堆顶数据与堆的最后一个数据交换，然后对根位置进行一次堆的向下调整，但是调整时被交换到最后的那个最大的数不参与向下调整。
2、完成步骤1后，这棵树除最后一个数之外，其余数又成一个大堆，然后又将堆顶数据与堆的最后一个数据交换，这样一来，第二大的数就被放到了倒数第二个位置上，然后该数又不参与堆的向下调整…反复执行下去，直到堆中只有一个数据时便结束。此时该序列就是一个升序。
实例：
将下面这组数先建大堆，再排升序
动图演示：（动图来自菜鸟网站->堆排序）
堆排序代码：
//堆排序
void HeapSort(int* a, int n)
{
//排升序，建大堆
//从第一个非叶子结点开始向下调整，一直到根
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
int end = n - 1;//记录堆的最后一个数据的下标
while (end)
{
Swap(&a[0], &a[end]);//将堆顶的数据和堆的最后一个数据交换
AdjustDown(a, end, 0);//对根进行一次向下调整
end--;//堆的最后一个数据的下标减一
}
}
时间复杂度： O ( N l o g N ) 空间复杂度： O ( 1 )
3.3.2 TOP-K问题
TOP-K问题：即求数据集合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等
我们从时间和空间的角度逐步来看：
假设当前我们输入数组
arr[2，7，4，6，2，3，9，8]，找出其中最大的k个数。
例如，将k设为4，则在这8个数字中，最大的k个数是6、7、8 、9。
这就是所谓的TOP-K问题
角度一
对于Top-K问题，能想到的最简单直接的方式就是排序，利用时间复杂度较低的堆排序将数组排为降序，然后输出前k个数就可以了
代码：
//交换函数
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//堆的向下调整（小堆）
void AdjustDown(int* a, int n, int parent)
{
//child记录左右孩子中值较小的孩子的下标
int child = 2 * parent + 1;//先默认其左孩子的值较小
while (child < n)
{
if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小
{
child++;//较小的孩子改为右孩子
}
if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小
{
//将父结点与较小的子结点交换
Swap(&a[child], &a[parent]);
//继续向下进行调整
parent = child;
child = 2 * parent + 1;
}
else//已成堆
{
break;
}
}
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
*returnSize = k;
int i = 0;
//建小堆
for (i = (arrSize - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, arrSize, i);
}
//排降序
int end = arrSize - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
AdjustDown(arr, end, 0);
end--;
}
//将最大的k个数存入数组
int* retArr = (int*)malloc(sizeof(int)*k);
for (i = 0; i < k; i++)
{
retArr[i] = arr[i];
}
return retArr;//返回最大的k个数
}
时间复杂度： O ( N + N l o g N )
【建堆为N，向下调整一次为log N,调整N次为NlogN，所以时间复杂度为O ( N + N l o g N ) 】
空间复杂度： O ( N )
————————————————
角度二
在角度一的基础上，我们可不可以将时间复杂度再降低一些？
我们可以将数组建成一个大堆，因为堆顶的元素最大，所以我们取k次堆顶的元素就可以实现要求了，即把N个数建堆，取出前k个
注意：
1.取出数据后要让其与最后的元素替换，因为你已经取出这个元素了，所以不需要它了，这时让它去堆尾，不让它算入堆的个数中就行了。
2. 如果在取到堆顶数据后直接删除数据，那么就要重新建堆了。正确的做法应该是上面所说的方法，因为那样只要进行一次向下调整，就可以保证堆的结构了。要知道建堆的复杂度为O(N),而一次向下调整的复杂度仅为O（logn），这样大大提升了效率。
代码：
//交换函数
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//堆的向下调整（大堆）
void AdjustDown(int* a, int n, int parent)
{
//child记录左右孩子中值较大的孩子的下标
int child = 2 * parent + 1;//先默认其左孩子的值较大
while (child < n)
{
if (child + 1 < n&&a[child + 1] > a[child])//右孩子存在并且右孩子比左孩子还大
{
child++;//较大的孩子改为右孩子
}
if (a[child] > a[parent])//左右孩子中较大孩子的值比父结点还大
{
//将父结点与较大的子结点交换
Swap(&a[child], &a[parent]);
//继续向下进行调整
parent = child;
child = 2 * parent + 1;
}
else//已成堆
{
break;
}
}
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
*returnSize = k;
int i = 0;
//建大堆
for (i = (arrSize - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, arrSize, i);
}
//将最大的k个数存入数组
int* retArr = (int*)malloc(sizeof(int)*k);
int end = arrSize - 1;
for (i = 0; i < k; i++)
{
retArr[i] = arr[0];//取堆顶数据
Swap(&arr[0], &arr[end]);//交换堆顶数据与最后一个数据
//进行一次向下调整，不把最后一个数据看作待调整的数据，所以待调整数据为end=arrSize-1
AdjustDown(arr, end, 0);
end--;//最后一个数据的下标改变
}
return retArr;//返回最大的k个数
}
时间复杂度：O(N+klogN)
空间复杂度：O(N)
角度三
如果数据量非常大，将会占用的内存是巨大的，上面的排序就不太可取了。
我们可以用下面的方法：
- 用数据集合中前K个元素来建堆
- 前k个最大的元素，则建小堆
- 前k个最小的元素，则建大堆
- 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
我们以找出最大的k个数为例：先建一个k个数的小堆，然后将数组中n-k个元素依次与堆顶的元素比较，若比堆顶元素大，则把堆顶元素换为该元素，然后再进行一次向下调整，使其仍为小堆。那么问题来了，为什么不用大堆呢，其实这很容易理解，如果建一个大堆，万一堆顶的数据就是我们所求的k个数中的一个，那么我们所求的k个数中比它小的数就永远不可能入堆，因此要用小堆来解决这个问题。
代码：
//交换函数
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//堆的向下调整（小堆）
void AdjustDown(int* a, int n, int parent)
{
//child记录左右孩子中值较小的孩子的下标
int child = 2 * parent + 1;//先默认其左孩子的值较小
while (child < n)
{
if (child + 1 < n&&a[child + 1] < a[child])//右孩子存在并且右孩子比左孩子还小
{
child++;//较小的孩子改为右孩子
}
if (a[child] < a[parent])//左右孩子中较小孩子的值比父结点还小
{
//将父结点与较小的子结点交换
Swap(&a[child], &a[parent]);
//继续向下进行调整
parent = child;
child = 2 * parent + 1;
}
else//已成堆
{
break;
}
}
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
*returnSize = k;
if (k == 0)
return NULL;
//用数组的前K个数建小堆
int i = 0;
int* retArr = (int*)malloc(sizeof(int)*k);
for (i = 0; i < k; i++)
{
retArr[i] = arr[i];
}
for (i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(retArr, k, i);
}
//剩下的N-k个数依次与堆顶数据比较
for (i = k; i < arrSize; i++)
{
if (arr[i]>retArr[0])
{
retArr[0] = arr[i];//堆顶数据替换
}
AdjustDown(retArr, k, 0);//进行一次向下调整
}
return retArr;//返回最大的k个数
}
时间复杂度：O（k+n*logk）
空间复杂度：O（n）
与之前两种方法对比，这种方法大大提高了效率。
4.二叉树链式结构的实现
链式二叉树，那必须得有自己的结点类型，以下是链式二叉树结点类型的定义，下面的问题都统一使用该结点类型。
//二叉树的链式结构
typedef int BTDataType;//结点中存储的元素类型（以int为例）
typedef struct BinaryTreeNode
{
BTDataType data;//结点中存储的元素类型
struct BinaryTreeNode* left;//左指针域（指向左孩子）
struct BinaryTreeNode* right;//右指针域（指向右孩子）
}BTNode;
在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入，此处先手动快速创建一棵简单的二叉树，方便我们学习。
BTNode* BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
//自建二叉树
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode('A');
BTNode* node2 = BuyNode('B');
BTNode* node3 = BuyNode('C');
BTNode* node4 = BuyNode('D');
BTNode* node5 = BuyNode('E');
BTNode* node6 = BuyNode('F');
BTNode* node7 = BuyNode('G');
node1->left = node2;
node1->right = node3;
node2->left = node4;
node3->left = node5;
node3->right = node6;
node4->left = node7;
return node1;
}
下面的学习以上面自建的二叉树为准
4.1二叉树的深度优先遍历
前序遍历
前序遍历，又叫先根遍历。
遍历顺序：根 -> 左子树 -> 右子树
代码：
//二叉树前序遍历
void PreOrder(BTNode* root) {
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
中序遍历
中序遍历，又叫中根遍历。
遍历顺序：左子树 -> 根 -> 右子树
代码：
// 二叉树中序遍历
void InOrder(BTNode* root)
{
if (root == NULL) {
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}
后序遍历
后序遍历，又叫后根遍历。
遍历顺序：左子树 -> 右子树 -> 根
代码:
// 二叉树后序遍历
void PostOrder(BTNode* root)
{
if (root == NULL) {
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}
4.2二叉树的广度优先遍历
层序遍历
层序遍历，从左往右逐层访问树的结点的过程就是层序遍历。
设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推。
思路（借助一个队列）：
借助队列先进先出的性质
1.先把根入队列，然后开始从队头出数据。
2.出队头的数据，把它的左孩子和右孩子依次从队尾入队列（NULL不入队列）。
3.重复进行步骤2，直到队列为空为止。
代码：(自己先写队列及相关功能)
//层序遍历
void BinaryLevelOrder(BTNode* root)
{
Queue q;
QueueInit(&q);//初始化队列
if (root != NULL)
QueuePush(&q, root);
while (!QueueEmpty(&q))//当队列不为空时，循环继续
{
BTNode* front = QueueFront(&q);//读取队头元素
QueuePop(&q);//删除队头元素
printf("%c ", front->data);//打印出队的元素
if (front->left)
{
QueuePush(&q, front->left);//出队元素的左孩子入队列
}
if (front->right)
{
QueuePush(&q, front->right);//出队元素的右孩子入队列
}
}
QueueDestroy(&q);//销毁队列
}
4.3 求节点个数以及高度等
4.3.1求二叉树节点个数
//1、遍历(前序) – 全局变量
int size = 0;
void BinaryTreeSize(BTNode* root)
{
if (root == NULL)
return;
else
++size;
BinaryTreeSize(root->left);
BinaryTreeSize(root->right);
}
int main()
{
BTNode* root = CreatBinaryTree();
//1.全局--缺点：第二次使用(例如查看另一颗树节点个数)，size值会继承上一次
BinaryTreeSize(root);
printf("BinaryTreeSize:%d\n", size);
BinaryTreeSize(root);
printf("BinaryTreeSize:%d\n", size);
}
// 2、遍历(前序) – 局部变量
传参时注意不能使用传值传参
void BinaryTreeSize(BTNode* root, int* psize)
{
if (root == NULL)
return;
else
++(*psize);
BinaryTreeSize(root->left, psize);
BinaryTreeSize(root->right, psize);
}
int main()
{
BTNode* root = CreatBinaryTree();
int size1 = 0;//局部
BinaryTreeSize(root, &size1);
printf("BinaryTreeSize:%d\n", size1);
int size2 = 0;//局部
BinaryTreeSize(root, &size2);
printf("BinaryTreeSize:%d\n", size2);
}
// 3.分治–利用递归(推荐使用)
int BinaryTreeSize(BTNode* root)
{
return root == NULL ? 0 : 1
+ BinaryTreeSize(root->left)
+ BinaryTreeSize(root->right);
}
int main()
{
BTNode* root = CreatBinaryTree();
BinaryTreeSize(root);
printf("BinaryTreeSize:%d\n", BinaryTreeSize(root));
BinaryTreeSize(root);
printf("BinaryTreeSize:%d\n", BinaryTreeSize(root));
}
4.3.2二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)//空树无叶子结点
{
return 0;
}
else if (root->left == NULL && root->right == NULL)//是叶子结点
{
return 1;
}
else
{
return BinaryTreeLeafSize(root->left)
+ BinaryTreeLeafSize(root->right);
}
}
int main()
{
BTNode* root = CreatBinaryTree();
printf("BinaryTreeLeafSize:%d\n", BinaryTreeLeafSize(root));
}
4.3.2二叉树第k层节点个数
思路：
相对于根结点的第k层结点的个数 = 相对于以其左孩子为根的第k-1层结点的个数 + 相对于以其右孩子为根的第k-1层结点的个数。
int BinaryTreeLevelKSize(BTNode* root, int k)
{
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BinaryTreeLevelKSize(root->left, k - 1)
+ BinaryTreeLevelKSize(root->right, k - 1);
}
int main()
{
BTNode* root = CreatBinaryTree();
printf("BinaryTreeLevelKSize:%d\n", BinaryTreeLevelKSize(root, 4));
}
4.3.3 二叉树深度/高度
核心思想：max(左子树的深度，右子树的深度)+1
int BinaryTreeDepth(BTNode* root)
{
if (root == NULL)
{
return 0;
}
int leftDepth = BinaryTreeDepth(root->left);
int rightDepth = BinaryTreeDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
int main()
{
BTNode* root = CreatBinaryTree();
printf("BinaryTreeDepth:%d\n", BinaryTreeDepth(root));
}
4.3.4 二叉树查找值为x的节点
1.先判断根结点是否是目标结点。
2.再去左子树中寻找。
3.最后去右子树中寻找。
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* retLeft = BinaryTreeFind(root->left, x);
if (retLeft)
{
return retLeft;
}
BTNode* retRight = BinaryTreeFind(root->right, x);
if (retRight)
{
return retRight;
}
return NULL;
}
int main()
{
BTNode* root = CreatBinaryTree();
BTNode* ret = BinaryTreeFind(root, 'N');//找 N节点
if (ret)
{
printf("找到了\n");
}
else
{
printf("没有找到\n");
}
}
4.4二叉树的销毁
二叉树的销毁，与其他数据结构的销毁类似，都是一边遍历一边销毁。但是二叉树需要注意销毁结点的顺序，遍历时我们应该选用后序遍历.
若先销毁根结点，那么其左右子树就无法找到，也就无法销毁了。
销毁顺序应该为：左子树->右子树->根。
代码：
//二叉树销毁
void BinaryTreeDestroy(BTNode* root)
{
if (root == NULL)
return;
BinaryTreeDestroy(root->left);//销毁左子树
BinaryTreeDestroy(root->right);//销毁右子树
free(root);//释放根结点
}
5.二叉树基础oj练习题
学习完这些，就可以适当写一些二叉树相关的练习题了：二叉树基础oj练习题
二叉树的学习并未止步于此，还有二叉搜索树等相关更复杂的学习内容等着我们，对于二叉树初阶知识的分享就到这里了，拜拜！
万字好文，欢迎三连~~
– the End –
以上就是我分享的二叉树相关内容，感谢阅读！
本文收录于专栏：数据结构与算法
关注作者，持续阅读作者的文章，学习更多知识！
https://blog.csdn.net/weixin_53306029?spm=1001.2014.3001.5343
2022/2/9
————————————————