数据结构之二叉树

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; // 结点中的数据域
};

 2.二叉树概念及结构

2.1概念

一棵二叉树是结点的一个有限集合，该集合: 1. 或者为空 2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

 从上图可以看出：

1. 二叉树不存在度大于2的结点

2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

 2.2 特殊的二叉树：

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

2.3 二叉树的性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 个结点.

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 .

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有 ＝ ＋1

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= . (ps： 是log以2 为底，n+1为对数) 5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对 于序号为i的结点有：

1. 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点

2. 若2i+1=n否则无左孩子

3. 若2i+2=n否则无右孩子

堆

堆是一棵完全二叉树，堆中的每一个节点都满足堆性质，也就是每个节点的值都必须大于（或等于）或小于（或等于）其子节点的值。根据这个性质，堆可以分为两种类型：

大堆：在大堆中，每个父节点的值都大于或等于其子节点的值。因此，堆的根节点（即堆顶）包含了堆中的最大值。
小堆：在小堆中，每个父节点的值都小于或等于其子节点的值。因此，堆的根节点包含了堆中的最小值。

       1
     /   \
    3     6
   / \   / \
  5  9  8   13

在这个小堆中：

• 根节点1是最小的元素。
• 每个子节点3, 6的值都大于等于它们的父节点1的值。
• 这个性质适用于堆的所有层：例如，节点5, 9, 8, 13的值都大于等于它们各自的父节点3, 6的值。

这个小堆对应数组存储结构为1 3 6 5 9 8 13

下面是一个大堆的结构：

       13
     /    \
    9      8
   / \    / \
  5  3   6   1

对应数组结构为13 9 8 5 3 6 1

堆的树形结构只是一种抽象的概念，在实际的物理存储上，堆通常是以数组的形式来实现的

二叉树的实现

1.准备工作

还是三个文件

h文件中放我们所需要的结构

这里我们去实现二叉树时我们用数组会更简单些 

#pragma once
#include
#include
#include
#include
 
 
typedef int HPDataType;
 
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
 
void HPInit(HP* php);
void HPDestroy(HP* php);
// 插入后保持数据是堆
void HPPush(HP* php, HPDataType x);
HPDataType HPTop(HP* php);
 
// 删除堆顶的数据
void HPPop(HP* php);
 
bool HPEmpty(HP* php);

 2.初始化和销毁

初始化和销毁因为前边很多数据结构都用了，所以就很简单了

void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
 
}
void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
 
}

3.推入数据

推入数据的话和其他的没有太大的区别

没有空间就创建给4，有了如果满了就给2倍

void HPPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		//如果没有空间就创建新空间，空间为零给四否者是二倍
		size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
 
	php->a[php->size] = x;
	php->size++;
 
	AdjustUp(php->a, php->size - 1);
}

3.1向上调整

我们这里以小堆为例进行讲解：

当向堆中插入一个新元素后，为了维持小顶堆的性质（即父节点的值始终小于等于其子节点的值），可能需要进行元素的向上调整）。下面详细说明这个过程：

1.当一个新元素被加入到堆中时，它首先被放置在堆的末尾（即作为树的最底层的最右侧的叶子节点），以保持完全二叉树的形状。
2.比较新节点与其父节点的值：插入的新元素可能会破坏小顶堆的性质，此时需要将新元素与其父节点进行比较。对于数组中的节点 i（假设索引从0开始），其父节点的位置是 (i - 1) / 2。注意这里全是整数值，比如下标为2的元素，它的父节点就为0
3.如果新元素的值小于其父节点的值，那么就需要交换这两个节点的值，因为在小顶堆中父节点应当是小于或等于子节点的值
4.向上递归：继续将现在的节点位置（原父节点的位置，因为已经交换）与新的父节点进行比较，如果还是小新的父节点的值，继续交换。这一过程一直进行，直到新元素到达根节点，或新元素大于或等于其父节点的值。

 代码实现就是

//向上调整
void AdjustUp(HPDataType* a, int child)
{
	int parent = child / 2 - 1;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
 
}

3.2补充交换函数Swap

因为后边需要用到交换

所以我们就直接进行一个函数包装

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}

4.删除数据

堆默认规定，要删除根节点的数据

堆顶存放最小值，删除后，为了满足小堆的性质，接下来根节点存储的为次小值

由于堆是以数组的形式存储的，堆顶元素就是数组的第一个元素。删除堆顶元素后，需要保持堆的完整性和顺序特性

将堆的最后一个元素移动到堆顶：为了保持结构性质，堆的最后一个元素被移动到堆顶位置。这是因为在二叉堆中，我们希望维护一个完全二叉树的结构。使用最后一个元素来替代被删除的元素是一种简单且有效的方法，它保证了树的结构完整性。

移动最后一个元素到堆顶后，这个新的堆顶元素可能会破坏堆的顺序性质。为了恢复堆的性质，需要执行下沉操作。具体步骤如下：

比较新的堆顶元素与其子节点。
如果在最小堆中，新的堆顶元素比其子节点大，则它需要与其最小的子节点交换位置； 在最大堆中，如果新的堆顶元素比其子节点小，则它需要与其最大的子节点交换位置。
重复这个比较和交换过程，直至新的堆顶元素被移至正确的位置，也就是说，它不再比任何一个子节点大（在最小堆中）或小（在最大堆中）

void HeapPop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
    
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	Ajustdown(php->a,php->size,0);
}

4.1向下调整

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 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 = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

我们需要找小一点的孩子进行交换

1.子节点选择：计算左子节点的索引（child = parent * 2 + 1）。在二叉堆中，给定父节点索引为i的情况下，左子节点的索引为2*i + 1，右子节点的索引为2*i + 2。开始时，我们先考虑左子节点。
2.while循环：确保当前考虑的子节点索引没有超出数组的界限，如果有两个节点，判断右节点是否小于左节点，如果小，child++，后面让右孩子与父节点交换
3.更新parent索引为当前child的索引，继续向下遍历堆。更新child索引为新parent索引的左子节点，准备进行下一轮的比较。
4.结束循环：如果子节点的值不小于父节点的值，说明当前父节点的位置适当，堆的性质得以维持，此时循环可以终止。
5.对于每次AdjustDown调用，最坏情况下需要进行的比较和交换次数与堆的高度成正比，即O(log n)

6.AdjustDown操作的时间复杂度是O(log n)

这里的中间10圈出来是要去删除

 5.删除堆顶数据和探空

/ 删除堆顶的数据
void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
 
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
 
	AdjustDown(php->a, php->size, 0);
}
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}