目录

1. 树的概念

2. 二叉树概念

3. 二叉树的存储

3.1 顺序存储

3.2 链式存储

4. 堆

4.1 堆的概念

4.2 堆的实现

4.3 堆的排序

• 节点的度：一个节点含有的子树的个数，如A的度为6
• 叶节点（终端节点）：度为0的节点
• 分支节点（非终端节点）：度不为0的节点
• 父节点：对应子节点的父节点
• 子节点：对应父节点的子节点
• 兄弟节点：有相同父节点
• 堂兄弟节点：父节点在同一层
• 节点的祖先：从根到这个节点所经分支上的所有节点
• 节点的子孙：以某节点为根的子树中的任一节点
• 树的度：一棵树中，最大节点的度，如上图数的度为6
• 节点的层数：以根为第一层，依次类推
• 树的高度（深度）：树中节点的最大层数
• 森林：有m（m>0）棵互不交互的树的集合称为森林

1. 并查集就是一个森林
2. 树是递归结构
3. 子树是不相交的，除了根节点外，每个节点有且仅有一个父节点，N个节点的树有N-1条边

2. 二叉树概念

• 二叉树每个节点的度不大于2
• 满二叉树：二叉树的层数为k，节点数为2^k-1
• 完全二叉树：二叉树的前k-1层都是满的，第k层是连续的
• 对任一二叉树，若叶节点个数为n0，令度为2的节点数为n2，则 n0 = n2+1
• 二叉树第 i 层上最多有 2^(i-1) 个节点，深度为 h 的二叉树最大节点数为 2^h - 1 个节点
• 具有 n 个节点的满二叉树的深度 h = log2(n+1)

3. 二叉树的存储

3.1 顺序存储

 下标计算父子间关系：

leftchild = parent*2 + 1

rightchild = parent*2 + 2

parent = (child - 1)/2

3.2 链式存储

 

4. 堆

4.1 堆的概念

• 堆总是一颗完全二叉树
• 小根堆：堆中所有的父节点都小于等于子节点
• 大根堆：堆中所有的父节点都大于等于子节点

4.2 堆的实现

#include 
#include 
#include 
#include 

#define DEFAULT_CAPACITY 4

typedef int HPDataType;

typedef struct HeapNode
{
	HPDataType* data;
	int size;
	int capacity;
}HP;

void InitHeap(HP* php);
void DestoryHeap(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);

void InitHeap(HP* php)
{
	assert(php);
	php->data = (HPDataType*)malloc(sizeof(HPDataType) * DEFAULT_CAPACITY);
	php->size = 0;
	php->capacity = DEFAULT_CAPACITY;
}

void DestoryHeap(HP* php)
{
	assert(php);
	free(php->data);
	php->data = NULL;
	php->size = 0;
	php->capacity = DEFAULT_CAPACITY;
}

void Swap(HPDataType* pdata, int child, int parent)
{
	HPDataType tmp = pdata[child];
	pdata[child] = pdata[parent];
	pdata[parent] = tmp;
}

void AdjustUp(HPDataType* pdata, int child)
{
	//小根堆
	while (child > 0)
	{
		int parent = (child - 1) / 2;
		if (pdata[child] < pdata[parent])
		{
			Swap(pdata, child, parent);
			int t = child;
			child = parent;
		}
		else
		{
			break;
		}
	}
}

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		HPDataType* tmp = (HPDataType*)realloc(php->data, sizeof(HPDataType) * php->size * 2);
		if (tmp)
		{
			php->data = tmp;
			php->capacity *= 2;
		}
	}
	php->data[php->size] = x;
	php->size++;
	AdjustUp(php->data, php->size - 1);
}

void AdjustDown(HPDataType* pdata, int size, int parent)
{
	int child = parent * 2 + 1;
    //小根堆
	while (child < size)
	{
		if (child + 1 < size && pdata[child + 1] < pdata[child])
		{
			child++;
		}
		if (pdata[child] < pdata[parent])
		{
			Swap(pdata, child, parent);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(php->data, 0, php->size - 1);
	php->size--;
	AdjustDown(php->data, php->size, 0);
}

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->data[0];
}

bool HeapEmpty(HP* php)
{
	assert(php);
	if (php->size == 0)
		return true;
	return false;
}

int HeapSize(HP* php)
{
	assert(php);
	return php->size;
}

int main()
{
	HP* heap = (HP*)malloc(sizeof(HP));
	InitHeap(heap);
	int a[] = { 24, 34, 34, 35, 23, 11, 12, 45, 23, 43, 64, 12 };
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(heap, a[i]);
	}
		while (!HeapEmpty(heap))
	{
		printf("%d ", HeapTop(heap));
		HeapPop(heap);
	}    //按升序打印，降序则将代码改为大根堆
	DestoryHeap(heap);
    free(heap);
	heap = NULL;
	return 0;
}

4.3 堆的排序

目的：效率提高为为log2(n)

思路：先数组建堆，再堆排序

#include 
#include 
#include 

void Swap(int* pdata, int child, int parent)
{
	int tmp = pdata[child];
	pdata[child] = pdata[parent];
	pdata[parent] = tmp;
}

void AdjustUp(int* pdata, int child)
{
	//大根堆
	while (child > 0)
	{
		int parent = (child - 1) / 2;
		if (pdata[child] > pdata[parent])
		{
			Swap(pdata, child, parent);
			int t = child;
			child = parent;
		}
		else
		{
			break;
		}
	}
}

void AdjustDown(int* pdata, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && pdata[child + 1] > pdata[child])
		{
			child++;
		}
		if (pdata[child] > pdata[parent])
		{
			Swap(pdata, child, parent);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//测试要求：将数组用堆升序排序
//升序--大根堆
//降序--小根堆
int main()
{
	int a[] = { 23, 34, 54, 65, 21, 24, 64, 63, 93, 22 };
	//建堆
	int i = 0;
	int size = sizeof(a) / sizeof(a[0]);
    //建堆法1：时间复杂度 O(n*log2(n))
	//for (i = 1; i < size; i++)
	//{
	//	AdjustUp(a, i);
	//}
    //建堆法2：时间复杂度 O(n)
	for (i = (size - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, size, i);
	}
	//堆排序
	int end = size - 1;
	while (end > 0)
	{
		Swap(a, end, 0);
		AdjustDown(a, end, 0);
		end--;
	}
	for (i = 0; i < size; i++)
	{
		printf("%d ", a[i]);
	}
	printf("n");
	return 0;
}