数据结构---树，二叉树的简单概念介绍、堆和堆排序

树

树的概念和结构

结构

在我们将堆之前，我们先来了解一下我们的树。
我们的堆是属于树里面的一种，
树是一种非线性结构，是一种一对多的一种结构，也就是我们的一个节点可能有多个后继节点，当然也可以只有一个或者没有。我们的这些有限结点组成一个具有层次关系的集合，我们把它叫做树是因为他的结构和一颗倒挂的数很像。

1. 在我们的最上面的节点叫做根节点，他没有前驱。
2. 我们树的其他节点具有0个或者多个后继节点。但是在只有一个前驱节点。
3. 因此，树是递归定义的。
4. 数的子树是不能相交的。相交的话就是不是我们的树了，是另外一种结构–图。

树的一些概念

**结点的度：**一个结点含有的子树的个数称为该结点的度；
如上图：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）棵互不相交的树的集合称为森林；

树的表示

我们的树由于太过于有多个后继节点导致我们的树在构建的时候会比较麻烦，我们可以用我们的链表来表示，也可以用数组来表示。

链式

对与我们用链式来存储我们的树的话，就需要我们去去存储他的后继节点，但是我们这里的节点的每个后继节点数目不同，我们治理有一下个很好的方法-----孩子兄弟表示法。
就是我们只存下我们的第一个孩子节点，在定义一个兄弟节点，指向他的兄弟 节点，这样当我们的节点具有同一个节点时候我们第一个孩子节点就会是这个孩子链的头结点，我们沿着我们的兄弟指针就可以找到双亲的所有孩子节点。

typedef int DataType;
struct Node
{
 struct Node* firstChild1; // 第一个孩子结点
 struct Node* pNextBrother; // 指向其下一个兄弟结点
 DataType data; // 结点中的数据域
};

1
2
3
4
5
6
7
8

数组

我们这里用数组存储主要是利用了双亲和孩子节点的下标关系。主要是存储二叉树的。

二叉树的相关知识

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

1. 或者为空
2. 由一个根结点加上两棵别称为左子树和右子树的二叉树组成

特点：
3. 二叉树不存在度大于2的结点
4. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
一张有意思的图：

**特殊的二叉树：

**

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

二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 个结点.
2. 若规定根结点的层数为1，则深度为h的二叉树的最大结点数是 .2^(
3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n1, 度为2的分支结点个数为n2 ,则有 n2＝n1 ＋1
4. 对于孩子和双亲的关系，如果我们给每个节点都标都标上序号的话，如果为空我们也还是要为那个空节点保留下这个序号，我们就可以发现一个双亲和他们的孩子节点的下标关系**:左孩子=父亲+1；右孩子=父亲+2；**
   由于我们整数激素那取整 的关系，我们利用孩子节点来求我们的父亲就可以写成：父亲=（孩子-1）/2
5. 若规定根结点的层数为1，具有n个结点的满二叉树的深度，h= . (ps： 是log以2为底，n+1为对数)。

数组存储二叉树

我使用数组存储还是利用了二叉树的那条双亲和孩子的序号关系，我的通过计算下标就可以找到他们的双亲节点和孩子节点。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

如果我们的二叉树是一颗完全二叉树的话我们可以考虑用数组去存储，这样操作起来会方便很多。
当然我们的树越接近满二叉树，我们的数组存储效率会很高，空间浪费的会很少。但是我们的二叉树的不是一个完全二叉树的话我们的存储效率会低很多，我峨嵋你要按照双亲的关系来存储。那么那些空姐带你的地方我们是不可以存储值的。
下面我们要讲的堆就是一颗完全二叉树，适合用我们的数组去存储。

堆

堆的概念及结构

如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。
总来说就是我们的双亲节点的值总是大于（小于）我们的孩子节点，
如果双亲总是大于我们的孩子节点就是大堆；
双亲小于孩子节点的话就是小堆；

现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统
虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。


第一个是小堆，第二个是大堆。
堆的性质：

1. 堆中某个结点的值总是不大于或不小于其父结点的值；
2. 堆总是一棵完全二叉树。

堆的实现

我们实现我们的堆采用的是数组去存储的，维护我们堆的结构体：

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* _a;
	int _size;//数组里面有多少个有效数值
	int _capacity;//数组的空间大小
}Heap;

1
2
3
4
5
6
7
8

我们下面将我们堆实现的一些接口：

void HeapInit(Heap* php);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
//进行调整（小堆）,向上调整
void AdjustUp(HPDataType* data, int child);
//交换
void Swag(int* a, int* b);
//向下调整
void AdjustDown(HPDataType* data, int parents, int size);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

初始化

我们的初始化就是给我们结构体中的数组开辟空间，不开也行，给我们的指针置空。

代码：

//堆的初始化
void HeapInit(Heap* php)
{
	assert(php);
	php->_a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
	php->_capacity = 4;
	php->_size = 0;
}
1
2
3
4
5
6
7
8

堆的销毁

我们的销毁就是将我们的申请的空间还给我们的操作系统就行，我们这里主要申请的空间就是我们的数组，只需要将我们的数组释放就行。

代码：

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_capacity = 0;
	hp->_size = 0;
}
1
2
3
4
5
6
7
8

堆的向下调整算法

我们的向下调整算法，有一个前提是L他们需要左右子树必须是堆，才好去调整。
int array[] = {27,15,19,18,28,34,65,49,25,37};我们这里建小堆
当我们的左右子树不是堆的时候就会导致他们的父子关系变化。
我们向下建堆的思想是我们的根和他的孩子中较小的进行比较，如果他大于那个较小的孩子就进行交换，，交换后该节点再继续和他交换后的新的孩子进行比较，如此一直到我们的这个节点小于他的较小的孩子节点或者一直到超出我们的书的最后的一个节点的下标(就是在我们树的最后一层，他没有孩子节点了)。
例子：

我们的小堆有一个特点是：我们的根节点是堆中最小的数值，这是因为我们的父亲节点一定小于孩子节点。
我峨嵋你大堆就是根接待你是数值最大的。

代码：

//向下调整，小堆
void AdjustDown(HPDataType* data, int parents,int size)
{
	assert(data);
	int child = parents * 2 + 1;
	while (child <= size-1)
	{
		if ( child + 1 <= size - 1 && data[child] > data[parents * 2 + 2])
			child = parents * 2 + 2;
		if (data[child] < data[parents])
		{
			//双亲比孩子大，交换
			Swag(&data[child], &data[parents]);
		}
		else {
			break;
		}
		parents = child;
		child = parents * 2 + 1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

堆的向上调整算法

我们的向上调整算法是从我们的最后一个节点来进行的。 我们找到最后一个节点的父亲（通过他们的下标的关系），我们将该节点进行比较，如果我们的节点比他的父亲节点小就进行交换，我们再继续和他的新父亲节点进行比较，一直到他的父亲节点小于他，或者我们这个节点来到了我们根节点的位置。

这里需要注意的循环条件的判定，如果你是>=0的话就会导致死循环，当年我们该节点来到我们的根节点位置下标为0，南无我们用公式去算他的父亲节点：（0-1）/2，由于取整的特点，这个的值还会是0，并不会小于0；

代码：

//向上调整(小堆)
void AdjustUp(HPDataType* data,int child)
{
	int parents = (child - 1) / 2;
	while (child > 0)
	{
		if (data[child] < data[parents])
		{
			//双亲大于孩子，要交换
			Swag(&data[child], &data[parents]);
			child = parents;
			parents = (parents - 1) / 2;
		}
		else {
			break;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

往堆中插入

我们往堆中插入是先将我们的插入的元素放在我们的数组的最后一个位置。我们插入了之后还要是我们的数组仍然是个堆，我们还要进行向上调整的操作，我们只需要调整刚进入的新的元素。形成一个新的堆。


代码：

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{

	assert(hp);
	int child = hp->_size;
	//判断空间是否充足
	if (hp->_capacity == hp->_size)
	{
		hp->_capacity = hp->_capacity * 2;
		hp->_a = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * hp->_capacity);
		if (hp == NULL)
		{
			perror("hp realloc!");
			return;
		}
	}
	//插入新的数据
	hp->_a[hp->_size] = x;
	hp->_size++;
	//小堆进行调整
	AdjustUp(hp->_a,child);

	
}
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

堆中元素的删除

我们删除元素如果删除我们的叶子节点显然是很容易的，所以我们要删除的我们的根节点。
但是如果我们的将我们的根节点删除的话，父子关系也会变乱，出现了你的兄弟节点成为了你的父亲节点，所以我们要先将我们的根节点和我们最后一个节点进行交换，再将我们的数组的大小改变，并不需要我们将值进行改变。交换之后，我们的数组也不是一个堆了，但是他的左右子树仍旧是一个小堆，这是我们就可以进行向下调整，重新将我们的数组变成一个新的堆。

代码：

// 堆的删除
void HeapPop(Heap* hp)
{
	//将根上面的值与我们的最后一个节点交换，在进行调整
	assert(hp);
	Swag(&hp->_a[0], &hp->_a[hp->_size - 1]);
	hp->_size--;
	AdjustDown(hp->_a,0, hp->_size);

}
1
2
3
4
5
6
7
8
9
10

取堆顶的数据

我们只需要将我们的数组中下标为0的元素返回就行
代码：

HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	return hp->_a[0];
}
1
2
3
4
5

堆的判空和数据个数

我们结构体中定义了一个size变量来记录我们元素的个数，只需要对这个只进行判断是否为0，

// 堆的数据个数
int HeapSize(Heap* hp) {
	assert(hp);
	return hp->_size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0 ? 1 : 0;
}
1
2
3
4
5
6
7
8
9
10
11