数据结构-二叉树以及堆和堆排序_堆和二叉排序树

树在数据结构中是一种很重要的存储结构，而树的种类有很多，例如：二叉树，哈夫曼树，b树，红黑树等等，而二叉树在数据结构中算是一种比较简单的树，而我们今天要了解的就是二叉树。

1.树的概念及结构

1.1 树的概念

树是一种非线性的数据结构，它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一颗倒挂的树，也就是他是根朝上，而叶朝下的。

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

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 树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间
的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法
等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

孩子表示法是一个结点内有一个存储数据的数据域，还有两个指针，一个指向孩子结点，一个指向兄弟结点。一个结点如果有多个孩子结点，那么孩子结点指针指向第一个孩子，剩下的孩子结点由兄弟结点连接，像链表一样。

代码表示

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};
1
2
3
4
5
6
7

2. 二叉树的概念及结构

2.1 概念

一颗二叉树是结点的一个有限集合，该集合：

1. 或者为空
2. 由一个根节点再加上两颗树别称为左子树和右子树的二叉树组成
   对于任意的二叉树都是由以下几种情况复合而成的：
   

2.2 特殊的二叉树

1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是
   说，如果一个二叉树的层数为K，且结点总数是2^k-1 ，则它就是满二叉树。
2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K
   的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对
   应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

满二叉树一定是完全二叉树的一种，但是完全二叉树不一定是满二叉树。

2.3 二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点。
2. 若规定根节点的层数为1，则深度为h的二叉树最大结点数是2^h-1。
3. 对任何一颗二叉树，如果度为0的结点个数设为n₀，度为2的结点个数设为n₂，则有n₀=n₂+1；
4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log₂(n+1);

2.4 二叉树的存储结构

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

1. 顺序存储
   顺序结构就是用数组来存储一颗树，但是我们一般存储的是完全二叉树，如果不是完全二叉树就会有空间上的浪费，为什么怎么说呢？请继续往下看。

树结构想存放在数组中是以从上至下从左至右的数组顺序对所有节点从0开始编号。

而我们父节点想找左右孩子结点怎么找呢？而孩子结点想找父节点怎么找呢？
其实这里面是有规律的，当我们父节点想找左孩子结点的时候，就用下标乘2加1。如果想找右孩子结点就是用下标乘2加2。例如：上图中第一个树中元素C在数组中的下标为2，那么F的位置就是2x2+1，G的位置就是2x2+2；
如果如果左孩子或者右孩子结点想找父节点就是下标减1除以二。例如：上图中第一个树G结点和F结点下标分别为5和6那么减一再除二就会等于C结点的下标
上图中的第二个树也是可以以数组的形式存储，但是会有空间上的浪费。

一般代码定义为：

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
1
2
3
4
5
6
7

2. 链式存储
   二叉树的链式存储结构就是用链表来存储一棵树，链表结点中有三个域，一个是用来存储元素的空间，还有两个指针，分别是指向左孩子和右孩子。
   
   一般也是用结构体来定义，具体代码

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;
1
2
3
4
5
6
7
8

3. 堆

3.1 堆的概念及结构

堆通常是一个可以被看做一棵树的数组对象。通俗的来讲，堆的逻辑结构就是一个完全二叉树，它与完全二叉树不同的是元素是按照一定的规律存放，否则不能叫做堆。而堆总是满足以下性质：

• 堆中的某个结点的值总是不大于或者不小于其父节点的值；
• 堆总是一颗完全二叉树。

堆也分为大堆(大根堆)和小堆(小根堆)

3.2 堆的实现

我们用代码实现堆一般使用数组来实现的，因为数组找父节点和子节点都很方便，方便我们建堆。
这个乱序的数组我们且先把他想象成一个完全二叉树，那么如何建堆，用什么样的算法

int array[] = {27,15,19,18,28,34,65,49,25,37};
1

我们假设先拿这个数组建一个大堆，那么就是每一个父节点都要大于等于孩子结点，我带大家一步一步来看。

1. 相信孩子结点找父节点和父节点找孩子节点大家在前面已经会了，我们先找到最后一个结点的父节点，也就是28，我们先构建假设以28为根节点的这个大堆，判断父节点是否大于等于孩子结点，如果不是找到左右孩子中较大的那个交换。
   

2. 把下标向前挪动也就到了18这个结点，我们构建建假设以28为根节点的这个大堆，判断父节点是否大于等于孩子结点，如果不是找到左右孩子中较大的那个交换。如果不换较大的49，把25换上去，大堆就不成立。
   

3. 把下标向前挪动也就到了19这个结点，我们构建建假设以19为根节点的这个大堆。
   

4. 把下标向前挪动也就到了15这个结点，我们构建建假设以15为根节点的这个大堆。
   

5. 把下标向前挪动也就到了27这个结点，我们就构建整个大堆，把27一直跟较大的那个孩子结点交换，一直到大堆的条件成立。
   
   这样就构建出了一个大堆。那我们思想有了，用代码是如何实现的呢？我带大家看一看

void swap(int* p1, int* p2) {
	int tem = *p1;
	*p1 = *p2;
	*p2 = tem;
}
//单趟排序
void AdjustDown(int* a, int n, int parent) {
	int child = parent * 2 + 1;
	while (child < n) {
		//防止越界，并且找出左右孩子较大的那个
		if (child+1 < n && a[child] < a[child + 1]) {
			child++; 
		}
		//如果孩子结点比父亲结点还要大，那么大堆不成立，就进行交换，否则跳出
		if (a[child] > a[parent]) {
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}
int main(){
	int array[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
	int i=0;
	int n=sizeof(array)/array(int);
	//初始值为28的下标，一直到根节点
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
		AdjustDown(a, n, i);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

3.3 堆的插入

我们会创建一个堆，那么插入数据到一个建好的堆中是如何实现的呢？其实也很简单，就是直接在数组尾部插入数据，然后和父节点进行判断，不满足大堆(小堆)和父节点进行交换，一直到满足条件否则到根节点为止。
例如：我们插入60这个元素，和父节点进行判断，不满足大堆就和父节点进行交换。

核心代码实现为

void AdjustUp(HPDataType* a, int child) {
	int parent = (child - 1) / 2;
	while (child > 0) {
		if (a[parent] < a[child]) {
			swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.4 堆的删除

堆的删除其实也非常简单，不废话直接给大家介绍如何实现的。

1. 从一个建好的堆当中删除数据，就是删除堆顶的数据，我们还是拿上面建好的大堆进行举例。
   
2. 再让堆顶的数据和最后一个数据进行交换
   
3. 再把28向下调整(具体怎么调整请看上面堆的创建单趟排序)，就变成下面这样
   

3.5 堆排序

我们会建一个大堆了那么小堆也是同样的道理。我们既然都学会如何创建一个堆了，不妨再说一说堆排序是什么原理，怎么实现的。

上图中是一个构建好的大堆，最大的元素始终在根节点的位置，也就是下标为0的位置，有什么好的方法能使整个数组有序呢？其实还是用了堆删除的思想。我们继续往下看。

1. 首先让最大的数65和最后一个下标的数28进行交换，就会变成如下图
   
   这样做的好处是什么呢，我们让最大的一个数到了最后一个位置，而且更重要的是没有破坏堆的结构，然后固定住65不要动了，最后一个下标的位置减一，变成了15，然后再把28向下调整(用上面代码的AdjustDown()函数)
   

这样就找出了第二大的元素，依次进行上面的操作，一直到数组元素只有一个为止。

3.6 堆代码链接

链接 (ps:可能要登录gitee账号才可以获取)

4. 二叉树的链式结构

二叉树的链式结构就比较简单了，我们直接看一看代码是如何定义的

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

1
2
3
4
5
6
7
8
9

其实链式二叉树它的功能主要是遍历和查找，

4.1 二叉树的创建

我们把字符串数组以递归的方式创建成链式一个二叉树。

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int* pi) {
	assert(a);
	if (a[*pi] == '#') {
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	root->_data = a[(*pi)++];
	root->_left = BinaryTreeCreate(a, pi);
	root->_right = BinaryTreeCreate(a, pi);

	return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4.2 前序、中序和后序遍历

我们这里遍历是用的递归遍历

//二叉树的前序遍历
void BinaryTreePrevOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	printf("%c ", root->_data);
	BinaryTreePrevOrder(root->_left);
	BinaryTreePrevOrder(root->_right);
}
//二叉树的中序遍历
void BinaryTreeInOrder(BTNode* root) {
	if (root == NULL) {
		printf("NULL ");
		return;
	}
	
	BinaryTreeInOrder(root->_left);
	printf("%c ", root->_data);
	BinaryTreeInOrder(root->_right);
}
//二叉树的后序遍历
void BinaryTreePostOrder(BTNode* root) {
	if (root == NULL) {
		return;
	}

	BinaryTreePostOrder(root->_left);
	BinaryTreePostOrder(root->_right);
	printf("%c \n", root->_data);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

4.3 二叉树的层序遍历

层序遍历需要借助队列来完成

void BinaryTreeLevelOrder(BTNode* root) {
	Queue q;
	QueueInit(&q);
	if (root) {
		//如果根节点不为空，插入队列
		QueuePush(&q, root);
	}
	//队列不为空继续
	while (!QueueEmpty(&q)) {
		BTNode* front = QueueFront(&q);
		//打印数据然后出队列
		printf("%c ", front->_data);
		QueuePop(&q);
		//左孩子不为空进队列
		if (front->_left) {
			QueuePush(&q, front->_left);
		}
		//右孩子不为空进队列
		if (front->_right) {
			QueuePush(&q, front->_right);
		}
	}
	QueueDestroy(&q);
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

4.4 链式二叉树源码

链接(ps:可能要登录gitee账号才可以获取)