数据结构初步（十）- 二叉树概念与堆的介绍

怠惰的未禾

发布于 2023-04-27 21:39:30

5540

发布于 2023-04-27 21:39:30

文章被收录于专栏：Linux之越战越勇

前言

本节将介绍树的概念，尽请期待！！！

1. 树

1.1 树的概念

树是一种非线性的数据结构，它由n个有限节点组成的一个具有层次关系的集合。因为这种数据结构像一颗倒挂起来的树，树根在上面，树枝和叶在下面，所以我们把这种数据结构称为树。

1.2 树的结构

树有一个特殊的节点，称为根节点，根节点没有前驱节点；除根节点外，其余节点被分成M个互不相交的集合T1、T2、…、Tm，其中每一个集合Ti（1<=i<=m）又是一颗结构与树类似的子树。每根子树的根节点有且只有一个前驱节点，可以有0个或多个后继节点； 树是递归定义的。一个有n个节点的数有n-1条边。

树形结构的子树中不能有交集。下图就不是树形结构：

1.3 树的相关概念简述

节点的度：一个节点含有的子树的个数。 叶子节点/终端节点：度为0的节点。 分支节点/非终端节点：度不为0的节点。 父节点/双亲节点：含有至少一个子节点的节点。 子节点：一个节点含有的子树的根节点，称为该节点的子节点。 兄弟节点：具有相同父节点的节点，互称为兄弟节点。 树的度：一棵树中最大节点的度。 节点的层次：从跟开始定义，根为第1层，根的子节点为第二层，…，以此类推。 数的高度或深度：树中节点的最大层次。 堂兄弟节点：父节点在同一层的节点。 节点的祖先：从根到该节点所经分支上的所有节点。 子孙：以某一节点为根节点的子树中所有节点都是该节点的子孙。森林：一颗及一颗以上的树组成的集合。

1.4 树的表示方法

树结构比较复杂，要储存表示就比较麻烦：既要保存值域，也要保存节点和节点之间的关系。 树的表示方法也有很多种：双亲表示法、孩子表示法、孩子双亲表示法、孩子兄弟表示法等。 使用静态指针数组

#define N 10
typedef int TDataType;
//静态结构体指针数组，事先规定了节点的度为N
typedef struct TreeNode{
	TDataType val;
    struct TreeNode* arr[N];
}TreeNode;

使用动态指针数组

#define N 10
typedef int TDataType;
//二级指针，用于开辟结构体指针数组，指向子节点
typedef struct TreeNode{
	TDataType val;
    struct TreeNode** arr;
}TreeNode;

孩子兄弟表示法

typedef int TDataType;
typedef struct TreeNode{
	TDataType val;
    struct TreeNode* child;
    struct TreeNode* brother;
};

孩子结构体指针child指向该节点的左边第一个子节点；兄弟结构体指针brother指向该节点的具有相同父节点的兄弟节点。

电脑中的文件系统目录就是树结构。

2. 二叉树

2.1 概念

二叉树是节点的有限集合：

为空，是空树
不为空，由一个根节点加上左子树和右子树的二叉树组成。

二叉树结点的度小于等于2。二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

二叉树的组成部分：

二叉树：

2.2 特殊二叉树

满二叉树

如果二叉树的每一层节点数都达到最大值，那么就称这个二叉树是满二叉树。对于层数从1开始，有K层的二叉树：如果该二叉树节点总数为(2^k )-1，该二叉树就是满二叉树。

完全二叉树

对于高度为K，有K个节点的二叉树，当且仅当其每一个节点都与深度为K的满二叉树中编号从1到n的节点一一对应时就说这个二叉树是完全二叉树。即共K层的二叉树，前K-层的节点都是满的，只有第K层的节点可以不是满的，且第K层节点从左到右是连续的。满二叉树是特殊的完全二叉树。
完全二叉树的节点数N的范围：2^(k-1) < N < 2^k - 1

2.3 二叉树的性质

假设根节点的层数为1：

则一颗非空二叉树的第K层上最多有2^(k-1)个节点；
高度为K的二叉树最大总节点数是(2^k) - 1;
对任意一棵树，如果度为0的叶节点个数为n0，度为2的分支节点个数为n2，则有n0 = n2+1；
具有n个节点的满二叉树的高度h，则h = log(n+1)；（以2为底，n+1的对数）
对于具有n个节点的完全二叉树，按照从上到下，从左到右的数组顺序对所有节点从0开始编号，对于编号为i的节点：
1. i=0时，i为根节点编号，无双亲节点；
2. i>0时，i位置节点的双亲编号：(i-1)/2;
3. 2i+1<n时，左孩子编号：2i+1；
4. 2i+2<n时，右孩子编号：2i+2；

3. 二叉树的储存结构

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

3.1 顺序结构

即使用数组来储存，一般使用数组只适合表示完全二叉树，不是完全二叉树时会有空间的浪费。 二叉树顺序储存在物理上是一个数组，在逻辑上是一个二叉树，与顺序表等线性表有着本质的不同。数据结构中的堆就是使用数组进行储存的。

非完全二叉树也可以使用数组来储存，只不过非完全二叉树里空缺的位置也需要考虑，空缺位置也需要在数组中占一个位置。这样相比完全二叉树储存来说，非完全二叉树储存在数组中，数组空间不能有效利用。

二叉树顺序储存实现

完全二叉树适合用数组储存，而普通的二叉树不适合用数组来储存，因为存在着不小的空间浪费。

堆的概念

堆是一种完全二叉树，但完全二叉树不一定是堆，堆通常使用顺序结构的数组实现。 数据结构的堆和操作系统中的堆是不同的两个概念，不要混为一谈。操作系统中的堆是操作系统对虚拟进程地址空间的划分，是内存的一个区域。如果有一个关键码的集合，K = {K_0，K_1，K_2，…，K_(n-1)}，把它的所有元素按完全二叉树顺序储存方式储存在一个一维数组中，并满足：k_i <= k(2i+1)且K_i <= k(2i+2)（或 k_i <= k(2i+1)且K_i <= k(2i+2)）i=0，1，2，…，则称为小堆（或大堆）。 并将根节点最大的堆称为最大堆或大根堆，根节点最小的堆称为最小堆或小根堆。

堆的结构

堆的某个节点的值总是不大于（对于大堆）或不小于其父节点（对于小堆）的值；
堆总是一颗完全二叉树，反之则不一定成立；

堆的实现

1. 使用向上调整算法建堆

在实现堆之前，我们得先建一个堆，或者小堆，或者大堆。但建堆也不是直接就能建的，就算已经给了顺序储存的数组，在逻辑上也只是一个完全二叉树，还不是一个堆。因为堆的根节点是整个二叉树元素中最小的或最大的，对应数组中就是第一个元素是最小的或最大的； 其余节点满足：

小堆中每个节点元素都不大于其孩子节点元素；
大堆中每个节点元素都不小于其孩子节点元素；

先来看看向上调整算法： 向上调整算法是啥？

向上调整的算法的思路： 注意：新元素能够向上调整的前提是新元素之前的所有元素代表的完全二叉树是一个堆。 对于一个给定的小堆，该堆使用数组连续存放。 如果想要向堆中增加一个元素K，并且需要保持新的堆还是小堆结构，那么我们就需要使用向上调整算法：

我们直接在数组最后面加上元素K。
让K与父节点元素比较，如果K小于父节点元素就交换两个节点的值；否则就结束调整，此时新的堆仍是小堆。
重复过程2，直到K到达根节点位置。

向上调整算法的时间复杂度：O(logN) 假设N为节点数，h为堆的高度 则有：2^h - 1 = N=> h = log(N+1)(以2为底，N+1的对数) 假如一个元素从堆底开始向上调整，该元素最终调整到堆顶。那么该元素最多调整h-1次，即log(N+1)-1次故时间复杂度是O(logN)

例如向上调整算法在小根堆中插入5的过程

向上调整算法代码

//向上调整
typedef int HPDataType;
//child是孩子元素下标
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;
		}
	}
}

如何使用向上调整算法建堆 我们已经知道向上调整算法的原理，它可以在堆中插入一个数并且新的堆也保持着堆的结构。 假设我们要建立大堆：

如果是一个空堆呢？一个元素也没有，也就是一个空树。

此时我们想空树里插入一个元素10，那么就成为了一个只有一个节点的堆。并且只有一个元素，也不需要进行调整，此时该二叉树既是大堆也是小堆。

再插入一个元素15呢？由于数组末尾插入元素15之前，该二叉树是一个大堆，所以可以从插入元素位置开始进行向上调整。 向上调整之后得到的还是大堆。

在插入一个元素9呢？在插入元素9之前的元素组成了大堆，故可以进行向上调整，但是由于9小于父节点元素15就停止向上调整。

插入元素的过程就是建立根堆的过程。 所以对于一个给定的数组，其中的元素连续存放，但并不是堆时，我们可以采用插入元素的方法来建堆：从根节点开始，一开始把数组看做空，接着依次插入数组中的元素到堆中(每次插入都借助向上调整算法)，当数组元素插入完时，该数组对应的堆也就建立起来了。
向上调整算法建堆的时间复杂度：O(N*logN) 以满二叉树为例：

2. 使用向下调整算法建堆

首先来看看向下调整算法。 向下调整算法是啥？

向下调整的算法的思路： 注意：元素能够向下调整的前提是： 元素的左子树和右子树是相同类型的堆（都是大堆或都是小堆）。因为这样左右子树的堆顶就是左右子树的最大值或最小值。左右子树的左右子树也符合堆顶是最大值或最小值，直到到达堆底。 以小堆为例： 比较该元素是否大于左右孩子的较大者，如果不大于就结束调整（因为此时左右孩子分别是左右子树的堆顶，也就是最小的）；如果大于就交换（该元素）和（左右孩子的较小者）。 继续进行当前元素和左右孩子的比较，直到到达堆底停止或提前结束调整。

例如删除堆顶元素时，堆重建时发生的向下调整：

向下调整算法的时间复杂度：O(logN) 假设N为节点数，h为堆的高度 则有：2^h - 1 = N=> h = log(N+1)(以2为底，N+1的对数) 假如一个元素从堆顶开始向下调整，该元素最终调整到堆底。那么该元素最多调整h-1次，即log(N+1)-1次故时间复杂度是O(logN)

向下调整代码

//向下调整
typedef int HPDataType;
//parent是父节点元素下标（编号）
void AdjustDown(HPDataType* a, int size, int parent) {
	int child = parent * 2 + 1;
	while (child < size - 1) {
		//小堆要找较小的孩子比较,大于孩子交换
		//大堆要找较大的孩子比较，小于孩子交换
		if (child+1 < size - 1 && a[child] < a[child+1]) {
			child++;
		}
		if (a[child] > a[parent]) {
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

如何使用向下调整算法建堆？ 我们已经知道一个堆中某一元素从堆顶不断通过向下调整，最终使堆保持了原来的特点（大堆或小堆）

由此得到一个节点元素想要进行向下调整，它的左右子树必须都是堆。 但是对于非堆的完全二叉树来说，从第一个元素（编号为0）来看，它的左右子树一般都不是堆，所以该元素不能进行向下调整；
同理，从其左右孩子来看，左右孩子的左右子树一般也不是堆，所以其左右孩子也不能够进行向下调整。
那么，什么时候可以呢？ 从某一个元素可以开始进行：该元素的左子树只有左孩子一个或没有左孩子，右子树也只有右孩子一个或没有右孩子。这个元素是最后一个元素的父节点，可以计算得出。
我们对于整个完全二叉树来说倒着找（满足左右子树是堆）节点元素进行向下调整。 当该元素调整完后在对该节点元素的上一个元素进行向下调整。直到把堆顶的元素调整完才结束。 对于数组来说，找上一个元素只需下标减1。

向下调整建堆的时间复杂度

所以对于一个给定的数组，其中的元素连续存放，但并不是堆时，从数组最后一个元素开始依次进行向下调整，直到遇到根节点结束。假设共有N个节点，堆的高度为h 向下调整算法建堆的时间复杂度：O(N)

3. 预防有文件被多次重复包含

#pragma once

或

#ifndef __HEAP__H__
#define __HEAP__H__
//...
#endif

4. 头文件的包含

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

5. 堆的结构体封装

typedef int HPDataType;
typedef struct Heap {
	HPDataType* pdata;
	int size;
	int capacity;
}Heap;

6. 堆的初始化

//堆初始化
void HeapInit(Heap* php) {
	assert(php);
	php->pdata = NULL;
	php->size = php->capacity = 0;

7. 堆数据的打印

//打印堆储存数据
void HeapPrint(Heap* php) {
	assert(php);
	for (int i = 0; i < php->size; ++i) {
		printf("%d ", php->pdata[i]);
	}
	printf("\n");
}

8. 输入元素到堆，并且保持堆的特点

//向上调整
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;
		}
	}
}

//输入数据到堆，并建堆
void HeapPush(Heap* php, HPDataType val) {
	//建堆
	assert(php);
	//判满
	if (php->size == php->capacity) {
		HPDataType newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->pdata, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL) {
			perror("realloc file");
			exit(-1);
		}
		php->pdata = tmp;
		php->capacity = newCapacity;
	}
	php->pdata[php->size] = val;
	++php->size;

	//向上调整
	AdjustUp(php->pdata, php->size - 1);
}

输入元素到堆，就是在堆底插入一个元素；对应于数组的末尾增加一个元素。 然后对该元素进行向上调整，找它的父节点，直到找到了根节点或者不满足调整的条件就结束调整。

9. 删除堆顶元素，并保持堆的特点

//向下调整
void AdjustDown(HPDataType* a, int size, int parent) {
	int child = parent * 2 + 1;
	while (child < size - 1) {
		//小堆要找较小的孩子比较,大于孩子交换
		//大堆要找较大的孩子比较，小于孩子交换
		if (child+1 < size - 1 && a[child] < a[child+1]) {
			child++;
		}
		if (a[child] > a[parent]) {
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

//删除堆顶元素
void HeapPop(Heap* php) {
	assert(php);
	Swap(&(php->pdata[0]), &(php->pdata[php->size - 1]));
	--php->size;

	//向下调整
	AdjustDown(php->pdata, php->size, 0);
}

删除堆顶的元素，是直接让堆顶元素与最后一个元素交换，数组有效程度减1,。堆顶元素在进行向下调整，直到堆底或者不满足调整条件就结束调整。

10. 取堆顶元素

//取堆顶元素
HPDataType HeapTop(Heap* php) {
	assert(php);
	assert(!HeapEmpty(php));
	return php->pdata[0];
}

11. 堆的大小

//堆的大小
int HeapSize(Heap* php) {
	assert(php);
	return php->size;
}

12. 判断堆是否为空

//判断堆是否为空
bool HeapEmpty(Heap* php) {
	assert(php);
	return php->size == 0;
}

堆的C语言实现

分文件实现，函数声明和定义分离 Heap.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int HPDataType;
typedef struct Heap {
	HPDataType* pdata;
	int size;
	int capacity;
}Heap;
//向上调整
void AdjustUp(HPDataType* a, int child);

//向下调整
void AdjustDown(HPDataType* a, int size, int parent);

//交换两个数
void Swap(HPDataType* pa, HPDataType* pb);

//堆初始化
void HeapInit(Heap* php);

//打印堆储存数据
void HeapPrint(Heap* php);

//堆的销毁
void HeapDestroy(Heap* php);

//输入数据到堆
void HeapPush(Heap* php, HPDataType val);

//删除堆顶元素
void HeapPop(Heap* php);

//取堆顶元素
HPDataType HeapTop(Heap* php);

//堆的大小
int HeapSize(Heap* php);

//判断堆是否为空
bool HeapEmpty(Heap* php);

Heap.c

#include "Heap.h"

//堆初始化
void HeapInit(Heap* php) {
	assert(php);
	php->pdata = NULL;
	php->size = php->capacity = 0;
}

//打印堆储存数据
void HeapPrint(Heap* php) {
	assert(php);
	for (int i = 0; i < php->size; ++i) {
		printf("%d ", php->pdata[i]);
	}
	printf("\n");
}

//堆的销毁
void HeapDestroy(Heap* php) {
	assert(php);
	php->pdata = NULL;
	php->size = php->capacity = 0;
}

void Swap(HPDataType* pa, HPDataType* pb) {
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = 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;
		}
	}
}

//输入数据到堆，并建堆
void HeapPush(Heap* php, HPDataType val) {
	//建堆
	assert(php);
	//判满
	if (php->size == php->capacity) {
		HPDataType newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->pdata, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL) {
			perror("realloc file");
			exit(-1);
		}
		php->pdata = tmp;
		php->capacity = newCapacity;
	}
	php->pdata[php->size] = val;
	++php->size;

	//向上调整
	AdjustUp(php->pdata, php->size - 1);
}

//向下调整
void AdjustDown(HPDataType* a, int size, int parent) {
	int child = parent * 2 + 1;
	while (child < size) {
		//小堆要找较小的孩子比较,大于孩子交换
		//大堆要找较大的孩子比较，小于孩子交换
		if (child+1 < size && a[child] < a[child+1]) {
			child++;
		}
		if (a[child] > a[parent]) {
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

//删除堆顶元素
void HeapPop(Heap* php) {
	assert(php);
	Swap(&(php->pdata[0]), &(php->pdata[php->size - 1]));
	--php->size;

	//向下调整
	AdjustDown(php->pdata, php->size, 0);
}

//取堆顶元素
HPDataType HeapTop(Heap* php) {
	assert(php);
	assert(!HeapEmpty(php));
	return php->pdata[0];
}

//堆的大小
int HeapSize(Heap* php) {
	assert(php);
	return php->size;
}

//判断堆是否为空
bool HeapEmpty(Heap* php) {
	assert(php);
	return php->size == 0;
}

堆的应用之堆排序

使用一个数组模拟堆，故该数组表示一个堆，可以方便的进行堆排序。堆排序是排序算法的一种，时间复杂度是O(N*logN)

堆排序借助堆的特点进行比较快速的排序：

可以借助向上调整或向下调整算法快速构建堆的数组形式；
堆顶是堆元素的最大值或最小值；
选择哪一种调整算法快速建堆？

向上调整建堆的时间复杂度是O(N*logN); 向下调整建堆的时间复杂度是O(N); 向下调整建堆时间复杂度较低，故我们选择向下调整算法快速建堆。

建堆的方法确定了，那么我们要建小堆还是大堆呢？

排升序建大堆； 排降序建小堆；

为什么？我们每次都只能拿堆顶的最值元素，然后需要再次建堆。

对于升序来说：需要元素从小到大。如果排升序建小堆，那么堆顶元素是堆中元素最小的。这时我们还需将剩余元素建堆排序，但是对于剩余元素来说，就不能保持小堆的结构了。所以我们需要重新建堆，而重新建堆的时间复杂度是O(N)，N个元素，建堆N次，时间复杂度是O(N^2)。堆的优势荡然无存，效率降到了普通排序的数量级，非常不可取。

如果建大堆，那么堆顶元素是最大的，直接就把堆顶元素与数组最后一个元素交换，之后不考虑旧堆顶元素，只考虑前剩余的元素，并且先前的堆的结构没有被破坏。重建堆只需要一个堆顶元素向下调整即可，而一个元素从堆顶调整到堆底时间复杂度也只需O(logN)次，而每个元素都进行一次，时间复杂度就是O(N*logN)。

对于降序来说：需要元素从大到小。建小堆，每次把堆顶最小的元素依次放到数组末尾，之后不考虑已经放到末尾的元素，再次建小堆直到每个元素都进行上述操作为止。建大堆，每次取到的是最大的元素，与升序建小堆时同理。
向下调整建堆：O(N*logN)

#include "Heap.h"

void HeapSort(int* a, int n) {
	//向下调整建堆
	//时间复杂度O(N*logN)

	//1.建堆,时间复杂度O(N)
	//升序建大堆，每次从堆顶拿最大的元素放在最后，该元素不再考虑
	//降序建小堆，每次从堆顶拿最小的元素放在最后，该元素不再考虑
	for (int i = (n-1-1)/2; i >= 0; --i) {
		AdjustDown(a, n, i);
	}
	//2.在数组未排序元素中 选择 堆顶元素，每次选择之后重新建堆,时间复杂度O(N*logN)
	for (int i = 1; i < n; ++i) {
		Swap(&a[0], &a[n - i]);
		AdjustDown(a, n - i, 0);
	}
}

向上调整建堆：O(N^2*logN)

#include "Heap.h"

void HeapSort(int* a, int n) {
	//向上调整建堆
	//时间复杂度O((N^2)*logN)

	//1.建堆O(N*logN)
	for (int i = 1; i < n; ++i) {
		AdjustUp(a, i);
	}
	//2. 选择元素再建堆
	for (int i = 1; i < n; ++i) {
		Swap(&a[0], &a[n - i]);
		for (int j = 0; j < n-i; ++j) {
			AdjustUp(a, j);
		}
	}
}

堆应用之堆的TopK

TOP-K问题：求前K个最大的元素或者最小的元素，一般情况下数据量都比较大。对于Top-K问题，可以使用排序，但是如果数据量非常大，排序效率就不高了(可能数据都不能一下子全部加载到内存中)。 思路1：

对前K个元素向下建堆 前k个最大的元素，则建小堆 前k个最小的元素，则建大堆
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

我们选择向下调整建堆算法，因为向下调整建堆算法时间复杂度较低，为O(K) 假设剩余N-k个元素都要交换并重新建堆，总的次数：(N-K)*(logK) 故Topk时间复杂度：O(N) 空间复杂度：O(1)

//TopK问题
//在N个最大（最小）的里面找最大的（最小的）前K个
void PrintTopK(int* a, int n, int k) {
	//方法1.向下建小堆一次，
	//然后循环与堆顶元素比较，如果大于堆顶元素，就替换堆顶再向下调整，直到循环结束
	for (int i = (k - 1 - 1) / 2; i >= 0; --i) {
		AdjustDown(a, k, i);
	}

	for (int i = k; i < n; ++i) {
		if (a[i] > a[0]) {
			Swap(&a[i], &a[0]);
			AdjustDown(a, k, 0);
		}
	}
	for (int i = 0; i < k; ++i) {
		printf("%d ", b[i]);
	}
}

思路2：

对元素整体向上建堆K次，每次记录并替换堆顶元素，再次建堆。

时间复杂度为O(N*logN) 空间复杂度为O(N) 不过从元素整体中选出前几个，整体建堆面临的问题不是时间上的问题，而是空间上的问题：空间复杂度O(N)，在数据量很大时，内存里一次可能放不下，这时只能多次读取数据，先选出每次读取数据中的前K个，再在多个前K个数据中找整体的前K个，比较麻烦。

//TopK问题
//在N个最大（最小）的里面找最大的（最小的）前K个
void PrintTopK(int* a, int n, int k) {
	//方法2.向上建堆，每次Pop堆顶，再次建堆
    //b储存最大的k个元素
	int* b = (int*)calloc(k, sizeof(int));
	if (b == NULL) {
		perror("malloc file");
		exit(-1);
	}
    //向上建堆
	for (int i = 0; i < n; ++i) {
		AdjustUp(a, i);
	}
	//每次记录堆顶元素到额外数组b中，在把堆顶元素交换到数组尾，只考虑前面的元素再次建堆
	for (int i = 0; i < k; ++i) {
		b[i] = a[0];
		Swap(&a[0], &a[n - i - 1]);
		for (int j = 0; j < n-i-1; ++j) {
			AdjustUp(a, j);
		}
	}
    
	for (int i = 0; i < k; ++i) {
		printf("%d ", b[i]);
	}
    free(b);
    //b = NULL;
}

那么，为了解决思路2的空间问题，那么有了思路3.

思路3：

对前K个元素向上建堆 前k个最大的元素，则建小堆 前k个最小的元素，则建大堆
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素 将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

时间复杂度：O(N^2*logN),时间复杂度太高

//TopK问题
//在N个最大（最小）的里面找最大的（最小的）前K个
void PrintTopK(int* a, int n, int k) {
	//方法3.向上建K个元素的小堆，再依次与后K-1个元素比较，
	//如果后K-1个元素满足大于堆顶元素时就交换堆顶元素和该元素，并重新建堆
	for (int i = 0; i < k; ++i) {
		AdjustUp(a, i);
	}
	for (int i = k; i < n; ++i) {
		if (a[0] < a[i]) {
			Swap(&a[0], &a[i]);
			for (int j = 0; j < k; ++j) {
				AdjustUp(a, j);
			}
		}
	}
    
	for (int i = 0; i < k; ++i) {
		printf("%d ", a[i]);
	}
}

3.2 链式储存

即用链表来表示一颗二叉树，用链指示元素的逻辑关系。 通常链表中每个节点由三个域组成：数据域、左指针域和右指针域。左右指针分别储存该节点左孩子和右孩子所在链节点的地址。链式结构分为二叉链表和三叉链表。其中三叉链表比二叉链表多了一个指针，这个指针指向了该节点的父节点，即储存了父节点的地址。

二叉链表节点

//二叉链表节点
typedef int BTDataType;
typedef struct BinaryTreeNode{
	BTDataType data;//储存的值
    struct BinaryTreeNode* left;//指向当前节点左孩子
    struct BinaryTreeNode* right;//指向当前节点右孩子
}BTNode;

三叉链表节点

//三叉链表节点
typedef int BTDataType;
typedef struct BinaryTreeNode{
	BTDataType data;//储存的值
    struct BinaryTreeNode* left;//指向当前节点的左孩子
    struct BinaryTreeNode* right;//指向当前节点的右孩子
    struct BinaryTreeNode* parent;//指向当前节点的双亲节点
}BTNode;

二叉树链式结构的实现 - Binary Tree

1. 所需头文件

程序运行所需头文件。

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

2. 二叉树节点类型

在使用二叉树之前我们需要先在内存创建出一棵二叉树来。 创建二叉树之前需要先定义二叉树节点结构体类型： 我们可以知道，一个二叉树节点需要包括一个储存数据的变量、一个指向左孩子节点的指针、一个指向右孩子节点的指针。

typedef int BTDataType;
typedef struct BTNode {
	BTDataType val;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;

3. 二叉树的临时创建

我们先来手动在内存构建一个二叉树，虽然粗糙，但是管用。自动实现二叉树的创建请见遍历之后的真 - 二叉树的创建。

BTNode* CreatTree() {
	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
	assert(n1);
	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
	assert(n2);
	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
	assert(n3);
	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
	assert(n4);
	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
	assert(n5);
	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
	assert(n6);
	BTNode* n7 = (BTNode*)malloc(sizeof(BTNode));
	assert(n7);

	//初始化左右指针为NULL
	n1->left = n1->right = NULL;
	n2->left = n2->right = NULL;
	n3->left = n3->right = NULL;
	n4->left = n4->right = NULL;
	n5->left = n5->right = NULL;
	n6->left = n6->right = NULL;
	n7->left = n7->right = NULL;

	//手动赋值
	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;
	n5->val = 5;
	n6->val = 6;
	n7->val = 7;

	//手动控制节点左右指针指向
	n1->left = n2;
	n1->right = n3;
	n2->left = n4;
	n2->right = NULL;
	n3->left = n5;
	n3->right = n6;
	n4->left = n7;
	n4->right = NULL;
	n5->left = NULL;
	n5->right = NULL;
	n6->left = NULL;
	n6->right = NULL;
	n7->left = NULL;
	n7->right = NULL;
	return n1;
}

4. 二叉树的递归遍历 - 前序/中序/后序

a. 先序遍历

先访问根，再访问左子树，最后访问右子树。注意：节点的左子树或右子树如果不存在，故叶子节点的左指针或右指针指向NULL，但实际遍历时其实也访问到了叶子结点的空子树，也就是访问到了NULL。

先序遍历过程图示

//前序遍历
void PreOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}

函数递归调用展开图：

b. 中序遍历

先遍历左子树，再遍历根节点，最后遍历右子树。

//中序遍历
void InOrder(BTNode* root){
	if (root == NULL) {
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

函数递归调用展开图：

c. 后序遍历

先遍历左子树，再遍历右子树，最后遍历根节点。

//后序遍历
void PostOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

5. 二叉树的循环遍历 - 层序遍历

层序遍历：设二叉树的根节点所在层数为1，从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第二层上的节点，接着是第三层的节点，…，从上到下，从左到右逐层访问树的所有节点。层序遍历我们采用循环实现。链式二叉树采用节点的方式链接，应该怎样依层次访问到二叉树每层节点呢？借助数据结构的队列可以方便实现： 队列的性质是前进先出，开始根节点先进队列，然后根节点再出队列，把该节点的左右孩子节点依次入队列； 也就是说，当一个节点出来时，可以把该节点的左右孩子节点也给带进队列（如果左右孩子节点存在的话）。 这样，从树根节点开始，在树根节点出队列时，顺便带左右孩子节点（第二层节点）入队列；第二层节点出队列完，同样把第三层节点也带入队列,…,直到最后一层节点也出队列，队列变为空，二叉树的循环遍历也就结束了。由于每次入队列都入的是节点本身，这存在着空间和时间的浪费，我们可以修改为每次入队列的是节点地址，而不是节点本身，这样可以加快入队列的效率，提高层序遍历的效率。

//层序遍历,即非递归遍历二叉树
void TreeLevelOrder(BTNode* root) {
	Queue q;
	QueueInit(&q);
    //树根节点不为NULL，就把该节点地址入队列
	if (root) {
		QueuePush(&q, root);
	}
	//当队列不为空时，说明二叉树还未遍历完
	while (!QueueEmpty(&q)) {
        //出队头，并用临时变量记录出队列节点地址
		BTNode* head = QueueHead(&q);
		QueuePop(&q);
		printf("%d ", head->val);
        //节点的孩子节点存在才需要入队列，所以这里需要判断一下
		if (head->left) {
			QueuePush(&q, head->left);
		}
		if (head->right) {
			QueuePush(&q, head->right);
		}
	}
	printf("\n");
}

6. 真 - 二叉树的创建

我们来自动构建一颗二叉树：通过给定的一个序列来自动构建，如：“1247####35##6##”通过先序遍历构建一棵二叉树。'#'表示空树

给出一个字符数组，构建二叉树的函数接受字符数组的首元素的地址、一个下标用于记录函数递归调用时对应的字符在字符数组的具体位置。 分治思想： 分为根和子树的创建、根对子树的链接。 关于下标我们需要传入的是下标的地址，而不能是下标本身。因为形参是实参的一份临时拷贝，形参的改变不会影响实参。我们需要递归调用完成二叉树的自动创建，实现节点之间的链接，那么记录字符数组的下标将会横跨整个函数递归调用过程，这个下标不能只在某一个递归函数中起作用，而是要在所有递归调用的函数中起作用，为此我们需要下标的地址才行。这本质是一个先序遍历

BTNode* TreeCreate(BTDataType * a, int* pi) {
    //当字符为#时，说明不存在节点，下标加1以记录下一个位置，返回NULL指针
	if (a[(*pi)] == '#') {
		(*pi)++;
		return NULL;
	}
    //节点存在时，先创建根节点，初始化节点指针，并对节点赋值
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL) {
		perror("malloc fail");
		return NULL;
	}
	root->left = root->right = NULL;
	root->val = a[(*pi)];
    //节点创建完成，下标加1以记录下一个位置
	(*pi)++;
    //先链接左节点，再链接右节点
	root->left = TreeCreate(a, pi);
	root->right = TreeCreate(a, pi);

	return root;
}

int main(){
	char str[] = "1247####35##6##";
	int i = 0;
    BTNode* root = TreeCreate(str, &i);
    if(root){
        //....
    }
}

7. 二叉树的节点个数

计数思想：借用一个全局整型变量计数，然后递归遍历每一个节点，遇到节点不是空数时计数变量加1.

int count = 0;

void TreeSize(BTNode* root) {
	if (root == NULL) {
		return;
	}
	count++;
	TreeSize(root->left);
	TreeSize(root->right);
}

分治思想： 求二叉树的节点个数，分解为求当前根和左右子树的节点个数的问题。 而左右子树又可以分为根和左右子树的问题…直到子树为空树。 对于当前根和子树的节点个数：当根为空时，节点个数为0；当根不为空时，节点个数为当前根节点+左子树节点数+右子树节点数；
本质为后序遍历： 丑图一张，只是表示递归调用过程。没用递归展开图的原因是有了代码才能画，而想要写出代码得先理解递归思路。

int TreeSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}

8. 二叉树的叶子节点个数

分治思想：当根节点为空数时，叶子节点为0；当根节点不为空时，如果根节点是叶子节点，叶子节点数为1；当前根不是叶子节点，叶子节点个数为 左子树叶子节点数 + 右子树叶子节点数

int TreeLeafSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	if (root->left == NULL && root->right == NULL) {
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

9. 二叉树第K层节点数

求第K层节点数，也就是求左右子树的第K-1层节点数的和，也就是求子树的子树的第K-2层节点数的和，直到k减到1时，就是第K层了。第k层节点数是相对来说的，对于每一层节点，K都会发生相应变化。如果根为空树，就返回0；

//求第k层的节点数，递归思想
int TreeKLevel(BTNode* root, int k) {
	assert(k > 0);
	if (root == NULL) {
		return 0;
	}
	if (k == 1) {
		return 1;
	}
	return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}

10. 二叉树的高度/深度

分治思想：求当前根节点的高度，就是求左子树高度与右子树高度中的最大值再+1；根节点为空树就返回0；

int TreeHeight(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	int heightleft = TreeHeight(root->left);
	int heightright = TreeHeight(root->right);
	return heightleft > heightright ? heightleft + 1 : heightright + 1;
}

11. 二叉树查找值为val的节点并返回节点地址

分治思想： 分为根和左右子树，前序遍历。 先找根，再找左子树，最后找右子树。 如果当前根节点为空树，就返回NULL；根节点不为空，如果根节点储存数据等于val，就返回根结点地址。根节点不为空，且根节点储存数据不为val，就先在左子树里找val，找到了（不为NULL）就返回找到的地址；找不到（为NULL）就去右子树里找val，找到了就返回找到的地址；整个树都找不到val，返回NULL。注意：左子树找到了之后就直接返回了，不再去找右子树。

//查找val并返回
BTNode* TreeFind(BTNode* root, BTDataType val) {
	if (root == NULL) {
		return NULL;
	}
    
	if (root->val == val) {
		return root;
	}
    //先在左子树里找，结果放在一个指针中
	BTNode* pL = TreeFind(root->left, val);
	if (pL) {
		return pL;
	}
    //先在右子树里找，结果放在一个指针中
	BTNode* pR = TreeFind(root->right, val);
	if (pR) {
		return pR;
	}
    
	return NULL;
}

12. 判断二叉树是否是完全二叉树

借助层序遍历判断是否是完全二叉树，因为递归实现层序遍历不太现实，递归一般都会走向树的深层次，然后再逐级返回，这与层序的依次访问每层的情况不太相符，并且是否是一颗树的情况多种多样，递归不能很好的对可能出现的情况进行全部的判断。
层序遍历时完全二叉树与非完全二叉树的情况有哪些不同？ 当我们在一个二叉树节点出队列时带入的左右孩子节点，在左右孩子不存在时也把不存在的情况**NULL**当做队列节点里存放的数据入队列。 完全二叉树在层序遍历结束后，队列中的节点存放的数据全是NULL；

非完全二叉树在遇到队列里节点存放的NULL数据时，队列里此节点之后的节点存放的数据不全是NULL，也就是还有节点未出队列。

//判断是否是完全二叉树
bool BinaryTreeComplete(BTNode* root) {
	Queue q;
	QueueInit(&q);
	//树根节点不为NULL，就把该节点地址入队列
	if (root) {
		QueuePush(&q, root);
	}
    //队列不为空时进行循环，遇到队列队头节点存放数据为NULL结束循环
	while (!QueueEmpty(&q)) {
		BTNode* head = QueueHead(&q);
		QueuePop(&q);
		if (head == NULL) {
			break;
		}
		QueuePush(&q, head->left);
		QueuePush(&q, head->right);
	}
    //判断队列队头储存元素是否全是NULL，不是就返回false，然后出队头
	while (!QueueEmpty(&q)) {
		BTNode* head = QueueHead(&q);
		QueuePop(&q);
        
		if (head != NULL) {
			QueueDestroy(&q);
			return false;
		}
	}

	QueueDestroy(&q);
	return true;
}

13. 二叉树的销毁

分治思想： 本质是后序遍历。 分为根和左右子树。 对于当前根节点来说，需要先销毁左子树，再销毁右子树，最后销毁根节点。

void BinaryTreeDestory(BTNode* root) {
	if (root = NULL) {
		return;
	}
	//后序
	//先销毁左子树，再销毁右子树
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

二叉树代码汇总

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include "Queue.h"

BTNode* TreeCreate(BTDataType * a, int* pi) {
	if (a[(*pi)] == '#') {
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL) {
		perror("malloc fail");
		return NULL;
	}
	root->left = root->right = NULL;
	root->val = a[(*pi)];
	(*pi)++;
	root->left = TreeCreate(a, pi);
	root->right = TreeCreate(a, pi);

	return root;
}

BTNode* TreeCreateIn(BTDataType* a, int* pi) {
	if (a[(*pi)] == '#') {
		(*pi)++;
		return NULL;
	}
	BTNode* left = TreeCreate(a, pi);

	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL) {
		perror("malloc fail");
		return NULL;
	}
	root->left = root->right = NULL;
	root->val = a[(*pi)];
	(*pi)++;
	root->left = left;

	BTNode* right = TreeCreate(a, pi);
	root->right = right;
	
	return root;
}

BTNode* CreateTree() {
	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
	assert(n1);
	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
	assert(n2);
	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
	assert(n3);
	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
	assert(n4);
	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
	assert(n5);
	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
	assert(n6);
	BTNode* n7 = (BTNode*)malloc(sizeof(BTNode));
	assert(n7);

	//初始化左右指针为NULL
	n1->left = n1->right = NULL;
	n2->left = n2->right = NULL;
	n3->left = n3->right = NULL;
	n4->left = n4->right = NULL;
	n5->left = n5->right = NULL;
	n6->left = n6->right = NULL;
	n7->left = n7->right = NULL;

	//手动赋值
	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;
	n5->val = 5;
	n6->val = 6;
	n7->val = 7;

	//手动控制节点左右指针指向
	n1->left = n2;
	n1->right = n3;
	n2->left = n4;
	n2->right = NULL;
	n3->left = n5;
	n3->right = n6;
	n4->left = n7;
	n4->right = NULL;
	n5->left = NULL;
	n5->right = NULL;
	n6->left = NULL;
	n6->right = NULL;
	n7->left = NULL;
	n7->right = NULL;
	return n1;
}

//递归遍历
//前序遍历
void PreOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	printf("%c ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root){
	if (root == NULL) {
		printf("NULL ");
		return;
	}

	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

//后序遍历
void PostOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}

	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

int TreeSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	return TreeSize(root->left) + TreeSize(root->right) + 1;
}

//
//int count = 0;
//
//void TreeSize(BTNode* root) {
//	if (root == NULL) {
//		return;
//	}
//	count++;
//	TreeSize(root->left);
//	TreeSize(root->right);
//}
//
//void TreeSize(BTNode* root) {
//	if (root == NULL) {
//		return;
//	}
//	static count = 0;
//	count++;
//	TreeSize(root->left);
//	TreeSize(root->right);
//}


int TreeLeafSize(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	if (root->left == NULL && root->right == NULL) {
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

int TreeHeight(BTNode* root) {
	if (root == NULL) {
		return 0;
	}
	int heightleft = TreeHeight(root->left);
	int heightright = TreeHeight(root->right);
	return heightleft > heightright ? heightleft + 1 : heightright + 1;
}

//求第k层的节点数，递归思想
int TreeKLevel(BTNode* root, int k) {
	assert(k > 0);
	if (root == NULL) {
		return 0;
	}
	if (k == 1) {
		return 1;
	}
	return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}

//查找val并返回
BTNode* TreeFind(BTNode* root, BTDataType val) {
	if (root == NULL) {
		return NULL;
	}
	if (root->val == val) {
		return root;
	}
	BTNode* pL = TreeFind(root->left, val);
	if (pL) {
		return pL;
	}
	BTNode* pR = TreeFind(root->right, val);
	if (pR) {
		return pR;
	}
	return NULL;
}

void BinaryTreeDestory(BTNode* root) {
	if (root = NULL) {
		return;
	}
	//后序
	//先销毁左子树，再销毁右子树
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

//层序遍历,即非递归遍历二叉树
void TreeLevelOrder(BTNode* root) {
	Queue q;
	QueueInit(&q);
	if (root) {
		QueuePush(&q, root);
	}

	while (!QueueEmpty(&q)) {
		BTNode* head = QueueHead(&q);
		QueuePop(&q);
		printf("%d ", head->val);
		if (head->left) {
			QueuePush(&q, head->left);
		}
		if (head->right) {
			QueuePush(&q, head->right);
		}
	}
	printf("\n");
}

//判断是否是完全二叉树
int BinaryTreeComplete(BTNode* root) {
	Queue q;
	QueueInit(&q);

	if (root) {
		QueuePush(&q, root);
	}
	while (!QueueEmpty(&q)) {
		BTNode* head = QueueHead(&q);
		QueuePop(&q);
		if (head == NULL) {
			break;
		}
		QueuePush(&q, head->left);
		QueuePush(&q, head->right);
	}
	while (!QueueEmpty(&q)) {
		BTNode* head = QueueHead(&q);
		QueuePop(&q);
		if (head != NULL) {
			QueueDestroy(&q);
			return 0;
		}
	}

	QueueDestroy(&q);
	return 1;
}

结语

本节主要介绍了数据结构中树的相关概念，主要是堆的实现与应用、二叉树的创建与遍历。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-03-22，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！