二叉树的顺序结构及实现

目录

1. 二叉树的顺序结构及实现

1.1 二叉树的顺序结构

1.2 堆的概念及结构

1.3 堆的实现

1.4 堆排序

---

1. 二叉树的顺序结构及实现

1.1 二叉树的顺序结构

       普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

1.2 堆的概念及结构

        如果将一些元素集合按照完全二叉树的顺序存储方式存储在一个一维数组中，并且满足任意一个节点的值总是不大于或不小于其父节点的值，则将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

总结堆的性质：
        ~堆中某个节点的值总是不大于或不小于其父节点的值；
        ~堆总是一棵完全二叉树

1.3 堆的实现

堆：

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

堆的初始化：

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

堆的销毁：

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

堆插入数据：

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(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType)*newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
 
		php->a = tmp;
		php->capacity = newcapacity;
	}
 
	php->a[php->size] = x;
	php->size++;
 
	AdjustUp(php->a, php->size - 1);
}

堆的删除：

void AdjustDwon(HPDataType* a, int size, int parent)//向下调整
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		// 选出左右孩子中小/大的那个
		if (child+1 < size && a[child+1] > a[child])
		{
			++child;
		}
 
		// 孩子跟父亲比较
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}	
}
 
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
 
	Swap(&(php->a[0]), &(php->a[php->size - 1]));
	php->size--;
 
	AdjustDwon(php->a, php->size, 0);
}

取堆顶元素：

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

判断堆是否为空：

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

求堆中元素个数：

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

1.4 堆排序

void HeapSort(int* a, int n)
{
    //向上，向下调整时间复杂度均为树高度，即logN
 
	// 建堆方式1：O(N*logN)
	//for (int i = 1; i < n; ++i)
	//{
	//	AdjustUp(a, i);
	//}
 
	// 建堆方式2：O(N)
	for (int i = (n-1-1)/2; i >= 0; --i)
	{
		AdjustDwon(a, n, i);
	}
 
	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
		--end;
	}
}
 
void TestHeapSort()
{
	int a[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
	HeapSort(a, sizeof(a) / sizeof(int));
}
 
int main()
{
	TestHeapSort();
 
	return 0;
}