【数据结构与算法】第8课—数据结构之二叉树(堆)
1. 树1. 什么是树？
[*]树是一种非线性的数据结构，它是由n(n>=0)个有限节点构成一个具有条理关系的聚集，一般是树根朝上，树叶朝下
[*]树有一个特别的节点，叫做根节点，根节点没有前驱节点
[*]树的根节点下面又有很多子节点，但是这些子节点是不相交的
[*]除根节点外，每棵子树的根节点有且只有一个前驱，但是可以有0个或多个后继，因此，树是递归定义的
https://i-blog.csdnimg.cn/direct/480572f95af54875b0587da328f20c9c.png
1.2 树的相关概念
[*]父节点/双亲节点：若一个节点有子节点，那么这个节点就是它子节点的父节点
[*]子节点/孩子节点：通俗点讲，就是一个节点它有父节点，那么它就是它父节点的子节点
[*]节点的度：就是该节点有几个子节点，那么它就是几度
[*]树的度：一棵树最大的节点的度
[*]叶子节点/终端节点：度为0的节点
[*]分支节点/非终端节点：除根节点外度不为0的节点
[*]兄弟节点：共同享有同一个父节点的节点
[*]节点的条理：从树的根开始，根为第1层，根的子节点为第2层，以此类推
[*]树的高度或深度：树中节点的最大条理
[*]节点的先人：从根到该节点所经分支上的所有节点
[*]森林：由m(m>0)棵互不相交的树的聚集
[*]路径：一条从书中任意节点出发，沿父节点到子节点的路径
https://i-blog.csdnimg.cn/direct/7be48fbaab04464f8a12b7104a442cdc.png
1.3 树的体现法
[*]这里主要先容常用的孩子兄弟体现法
[*]树有N个节点，有N-1条边
https://i-blog.csdnimg.cn/direct/8f629b9ea6cc45d590e9053945a9634a.png
2. 二叉树
[*]二叉树：是树中比较常用的一种树形结构
[*]二叉树的子树有左右之分，且序次不能颠倒
[*]二叉树之所以叫二叉树，是由于它每个节点的度最大为2，也就是每个节点最多有2个子节点
https://i-blog.csdnimg.cn/direct/77b5f7773168445cac49881de6dbe5c8.png
2.1 特别的二叉树
[*]满二叉树
[*]一个二叉树，如果每一层的节点数都达到最大值，则该二叉树就是满二叉树
[*]通俗点讲，就是一个二叉树的每一层的节点(除根节点外)都有它的兄弟节点，那么它就是满二叉树
[*]满二叉树满足：第N层的节点数是2^(N-1)个，树一共有2^N-1个节点
https://i-blog.csdnimg.cn/direct/3330e54e32e2412c94cbb443b2a5aba7.png
[*]完全二叉树
[*]完全二叉树就是有N个节点的二叉树，除最后一层外，其余层都是填满的状态，而且最后一层的节点都是从左到右依次分列，中间不答应有空隙
[*]满二叉树是一种特别的完全二叉树
https://i-blog.csdnimg.cn/direct/f234f11cae8048f2aeaea83572d09132.png
https://i-blog.csdnimg.cn/direct/2f8a89e36abd4b9bb60548a393ba3201.png
2.2 二叉树的性质
[*]若规定二叉树的根节点的层数为1，那么该树第k层共有2^(k-1)个节点
[*]若二叉树的根节点的层数为1，那么深度为k的树的最大节点数为2^k-1
[*]若二叉树的根节点的层数为1，那么具有n个节点的满二叉树的深度h=log2(n+1)(2为底，n+1为对数)
https://i-blog.csdnimg.cn/direct/768ddebb49804e92906e5fde16c92df0.png
2.3 二叉树的存储结构
[*]对于二叉树的存储结构一共有两种，一种是顺序结构，另一种是链式结构
[*]顺序结构存储
https://i-blog.csdnimg.cn/direct/d7e7a0fe30e34edfa1c21aa2acbd96df.png
[*]链式结构存储
[*]链式结构中，链表的每个节点都有3个域构成，数据域和左右指针域，左右指针分别指向左孩子节点和右孩子节点
[*]链式结构又分为二叉链和三叉链，三叉链比二叉链多了一个指向父节点的指针
https://i-blog.csdnimg.cn/direct/46e0cd255b37443ab3bb9608dee0763f.png
3. 实现顺序结构二叉树
3.1 堆的概念
[*]堆是一种特别的二叉树，也是完全二叉树，一般是把堆使用顺序结构来存储
[*]堆的底层结构是数组
[*]堆也有大堆和小堆之分，根节点最大的堆叫最大堆/大根堆，根节点最小的堆叫最小堆/小根堆
https://i-blog.csdnimg.cn/direct/519873cc72864c9faafa0d731e27c694.png
[*]堆的性质
[*]堆的某个节点值总是不大于或不小于其父节点的值
[*]堆总是一棵完全二叉树
[*]二叉树的性质
[*]对于有N个节点的完全二叉树，对于在下标0~k的数组中有：
https://i-blog.csdnimg.cn/direct/7f2bd5248c49473cbdeae1bcec356cd5.png
3.2 堆的实现
3.2.1 堆的数据结构
typedef int HeapDataType;
//堆的数据结构
typedef struct Heap
{
HeapDataType* arr; //动态数组
int size; //数组有效数据个数
int capacity; //数组容量大小
}Heap;
3.2.2 堆的初始化
//堆初始化
void HeapInit(Heap* pheap)
{
assert(pheap);
pheap->arr = NULL;
pheap->size = pheap->capacity = 0;
}
3.2.3 堆插入数据
https://i-blog.csdnimg.cn/direct/6e97cd14bbcf4055bc6a4662a32b8c4d.png
//交换值
void Swap(HeapDataType* p1, HeapDataType* p2)
{
HeapDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向上调整算法
void AdjustUp(HeapDataType* arr, HeapDataType child)
{
int parent = (child - 1) / 2;//定义父节点
while (child > 0)
{
//小堆
if (arr < arr)
{
Swap(&arr, &arr); //交换值
child = parent;//child走到父节点
parent = (child - 1) / 2;//parent走到更新后的child的父节点
}
else
break;
}
}
//堆插入数据
void HeapPush(Heap* pheap, HeapDataType x)
{
assert(pheap);
//如果数组满了/为空
if (pheap->size == pheap->capacity)
{
//定义数组容量
int newCapacity = pheap->capacity == 0 ? 4 : 2 * pheap->capacity;
//为数组申请空间
HeapDataType* tmp = (HeapDataType*)realloc(pheap->arr, sizeof(HeapDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc");
exit(1);
}
pheap->arr = tmp;//申请的空间赋给数组
pheap->capacity = newCapacity;//新容量大小赋给capacity
}
//插入数据
pheap->arr = x;
//向上调整
AdjustUp(pheap->arr, pheap->size);
pheap->size++;
}
3.2.4 删除堆顶数据
https://i-blog.csdnimg.cn/direct/fdd60df5808342d2a864c7dab2f1ff25.png
https://i-blog.csdnimg.cn/direct/755f81613cce4eb8847a7dc6db8d4169.png
https://i-blog.csdnimg.cn/direct/017651ab253f4902a203d6d375abf021.png
https://i-blog.csdnimg.cn/direct/37739b4c6fbc43cca9e5abb78b5db62d.png
//交换值
void Swap(HeapDataType* p1, HeapDataType* p2)
{
HeapDataType tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向下调整算法
void AdjustDown(HeapDataType* arr, HeapDataType parent, int n)
{
HeapDataType child = parent * 2 + 1;//孩子节点
while (child < n)
{
//找最大的孩子节点
if (child + 1 < n && arr < arr)
{
child++;
}
//如果子节点大于父节点(大堆)
if (arr > arr)
{
//交换父节点和子节点
Swap(&arr, &arr);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
//删除堆顶数据
void HeapPop(Heap* pheap)
{
assert(!HeapEmpty(pheap));
//交换堆顶元素和最后一个元素
Swap(&pheap->arr, &pheap->arr);
pheap->size--;
//向下调整
AdjustDown(pheap->arr, 0, pheap->size);
}
//取堆顶数据
HeapDataType HeapTop(Heap* pheap)
{
assert(pheap);
return pheap->arr;
}
3.2.5 堆的判空和求有用数据个数
//判空
bool HeapEmpty(Heap* pheap)
{
assert(pheap);
return pheap->size == 0;
}
//求有效数据个数
int HeapSize(Heap* pheap)
{
assert(pheap);
return pheap->size;
}
3.3 堆排序
[*]先建堆
https://i-blog.csdnimg.cn/direct/a88b649ce6b74afa8a7c5cba5bc454f3.png
https://i-blog.csdnimg.cn/direct/b7040d9ef24e4de4bbed95827b225647.png
[*]之所以升序要建大堆，是由于最后还需要将堆顶元素与最后元素交换，然后向下调整，具体操作如下：
[*]排序(升序)
[*]向下调整算法
https://i-blog.csdnimg.cn/direct/20ce6db47b8f4545a926380f3181697b.png
https://i-blog.csdnimg.cn/direct/33d3cde03ef243e7aadaf64d74443168.png
[*]堆排序时，每次首尾交换元素后，最后一个元素就是数的最大元素，因此在向下调整的过程中，child的限制条件为child<end,也就阐明child移动的过程中是不会到划定范围内的最后一个元素，由于那样child已经越界了，这样也就保证了首尾每次交换的都是划定范围内的最大元素，同理child的兄弟节点child+1<end，也要保证不能越界，end每次向下调整过后要-1
https://i-blog.csdnimg.cn/direct/ca9bbe112a66451a86bf14bfc97d8f18.png
//堆排序
void HeapSort(HeapDataType* arr, int sz)
{
//根据给定的arr建大堆
//child--sz-1parent--(sz-1-1)/2
for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(arr, i, sz);
}
//排升序：建大堆
//排降序：建小堆
//堆排序
int end = sz - 1;
while (end)
{
Swap(&arr, &arr);
AdjustDown(arr, 0, end);
end--;
}
}
int main()
{
int arr[] = { 34,18,88,23,67,45 };
int sz = sizeof(arr) / sizeof(arr);
HeapSort(arr,sz);//堆排序
return 0;
}
[*]向下调整算法的时间复杂度：O(logn),n为元素个数
[*]堆排序的时间复杂度：n*O(logn),n为元素个数，由于堆排序在建堆时要执行（sz-2）次向下调整算法
[*]向上调整(升序)
//向上调整算法
void AdjustUp(HeapDataType* arr, HeapDataType child)
{
int parent = (child - 1) / 2;//定义父节点
while (child > 0)
{
//大堆
if (arr > arr)
{
Swap(&arr, &arr); //交换值
child = parent;//child走到父节点
parent = (child - 1) / 2;//parent走到更新后的child的父节点
}
else
break;
}
}
//堆排序
void HeapSort(HeapDataType* arr, int sz)
{
//根据给定的arr建大堆
//child--sz-1parent--(sz-1-1)/2
//for (int i = (sz - 1 - 1) / 2; i >= 0; i--)
//{
// AdjustDown(arr, i, sz); //向下调整算法
//}
//向上调整算法
for (int i = 0; i < sz; i++)
{
AdjustUp(arr, i);
}
//排升序：建大堆
//排降序：建小堆
//堆排序
int end = sz - 1;
while (end)
{
Swap(&arr, &arr);
AdjustDown(arr, 0, end);
end--;
}
for (int j = 0; j < sz; j++)
{
printf("%d ", arr);
}
}
[*]总结
[*]向上调整算法建堆的时间复杂度为O(n*logn)
[*]向下调整算法建堆的时间复杂度为O(n)
[*]堆排序的时间复杂度为O(nlogn)
3.4 Top K题目
https://i-blog.csdnimg.cn/direct/1ab4b1837fe546b8929bab0fb6c767ac.png
[*]代码实现
//造数据
void CreateNdata()
{
int n = 100000;
srand((unsigned int)time(NULL));
FILE* fin = fopen("data.txt", 'w');
if (fin == NULL)
{
perror("fopen fail!\n");
return;
}
for (int i = 0; i < n; i++)
{
int x = (rand() + i) % 1000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
//求前k个数据
void TopK()
{
int k = 0;
printf("请输入k:");
scanf("%d", &k);
const char* file = "data.txt";
FILE* fout = fopen(file, 'r');
if (fout == NULL)
{
perror("fout");
exit(2);
}
//找最大的前K个数,建小堆
int* minHeap = (int*)malloc(k * sizeof(int));
if (minHeap == NULL)
{
perror("malloc");
exit(1);
}
//读取文件中的前k个数据建堆
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minHeap);
}
//建堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(minHeap, i, k);
}
//遍历剩下的n-k个数据，跟堆顶数据比较，谁大谁入堆
int x = 0;
while (fscanf(fout, "%d", &x) != EOF)
{
if (x > minHeap)
{
minHeap = x;
AdjustDown(minHeap, 0, k);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minHeap);
}
fclose(fout);
free(minHeap);
minHeap = NULL;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]