【数据结构】二叉树基本概念及堆的C语言模拟实现

1.二叉树的基础概念1.1二叉树的定义二叉树是一种比较特殊的树型结构二叉树树的每个结点的度最多有两个且有左右之分就像人的左右手一样因此我们可以知道二叉树是一颗有序树结点的左子树的根节点被称为左孩子右边的则为右孩子1.2特殊二叉树分类满二叉树:如果一颗二叉树的每一层都是满的除了叶子结点外的每个结点都有左右孩子那这颗二叉树则是一颗满二叉树假如这颗二叉树的层数为n的话那结点的数量就为2^n - 1如果上面我给的图就是一颗满二叉树完全二叉树完全二叉树是由满二叉树引出来的假设深度这课树有n个结点所有的结点有1到n开始编号对于任意结点与他相同深度的满二叉树的编号为1到n的结点位置相同的话那这颗树就是完全二叉树其实说白了就是把一颗满二叉树的叶子结点从右向左删除诺干个结点剩下的就是一颗完全二叉树了1.3二叉树的一些性质1如果规定这棵树的根节点层数为1的话那任意i层的最大结点数量为2^(i - 1)2同样规定这棵树的根节点层数为1假设深度为h那这棵树的最大结点数量为2^h - 1;3具有n个结点的满二叉树来说深度h long 2 (n 1) 以2为底的对数4假如这颗二叉树从0开始编号的话假设这个结点为i号结点如果父结点存在的话父结点的下标为 i - 1/ 2 如果左孩子存在的话左孩子的下标为 (2 * i ) 1, 如果右孩子存在的话那右孩子的下标为 2 * i 2这个性质很重要是我们理解顺序存储完全二叉树的基础1.4二叉树的存储二叉树的存储分为顺序存储与链式存储两种顺序存储普通的二叉树其实是不适合使用数组来存储的因为会造成很大的空间浪费比如我这里通过二叉树的性质计算下标来存储的话可以看到因为下标的存储不是连续的所以造成了空间的浪费而当这颗树是一颗完全二叉树时可以看到空间有效的被利用起来了所以完全二叉树更适合使用顺序存储而下面我们用C语言实现的堆就是完全二叉树的结构所以我们也使用顺序存储的方式来模拟实现一个堆。但是需要注意的是我们这里的堆是数据结构的堆而不是操作系统管理内存的那个堆区链式存储链式存储结构是指用链表来表示一颗二叉树一般每个结点有三个域数据域、左右指针域。数据域用于存储该结点的数据左右指针分别指向该结点的左孩子、右孩子。但这里我们暂时不用2.堆的概念及模拟实现2.1堆的概念前面也有说过堆是一个完全二叉树的存储结构可以大幅的优化我们的搜索比如实现Trie树的时候假如我们有一个集合用堆来存储{a1, a2, a3, a4, a5}, 那么这个集合在堆中应该满足根结点最大的堆被称为最大堆或者大根堆 根节点最小的被称为最小堆或者小根堆那小根堆是升序大根堆是降序吗需要注意的是并不是这样的因为我们并不限制兄弟之间的大小关系但我们可以借助堆来快速完成找出前几个最大的问题这种问题就是top-k问题。也有一种排序叫做堆排序在后面也会有介绍2.2堆的C语言模拟实现OK呀也是又又又又要造轮子实际在C中也为我们提供实现好的堆但我们可以通过模拟来加深一下对堆的理解以及了解一下向下调整算法和向上调整算法下面是堆的结构体定义和要实现的函数头文件这里我就以实现一个小根堆为目的了大根堆的实现方式和小根堆同理#pragma once #include stdio.h #include stdlib.h #include stdbool.h #include assert.h typedef int HeapDataType; typedef struct Heap { HeapDataType* a; int size; int capacity; }HP; //初始化与销毁 void HpInit(HP* php); void HpDestroy(HP* php); //建小根堆 void HpPush(HP* php, HeapDataType x); void HpPop(HP* php); //删除元素 HeapDataType HpTop(HP* php); //是否为空 bool HpEmpty(HP* php); int HpSize(HP* php); //交换元素、向上调整算法、向下调整算法 void Sawp(HeapDataType* a, HeapDataType* b); void AdjustUp(HeapDataType* a, int n); void AdjustDown(HeapDataType* a, int prent, int n);函数实现初始化与销毁void HpInit(HP* php) { assert(php); php-a NULL; php-capacity php-size 0; } void HpDestroy(HP* php) { assert(php); free(php-a); php-a NULL; php-capacity php-size 0; }这里的代码都很简单就不赘述了插入元素与向上调整算法void HpPush(HP* php, HeapDataType x) { assert(php); if (php-capacity php-size) { int newcapacity php-capacity 0 ? 4 : 2 * php-capacity; HeapDataType* tem (HeapDataType*)realloc(php-a, sizeof(HeapDataType) * newcapacity); if (tem NULL) { perror(malloc fail !); return; } php-a tem; php-capacity newcapacity; } php-a[php-size] x; php-size; AdjustUp(php-a, php-size - 1); }在插入元素前先判断一下空间是否足够不够就扩容这不是重点重点是我们该怎么样在插入一个元素之后继续维护这个堆。这里就该介绍我们的向上调整算法了。我们插入元素是在堆的叶子结点从左往右依次插入每插入一个元素时会破坏堆的有序性所以为了维护这个堆我们需要从下往上重新调整这个堆让这个堆重新有序。因为我们创建的是一个小根堆父结点是要比子结点要小的所以当子结点比父节点要小时就与父结点交换然后从小往上依次调整维护这个小根堆落实在代码上void AdjustUp(HeapDataType* a, int n) { int child n; int parent (child - 1) / 2; while (child 0) { if (a[child] a[parent]) { Sawp(a[child], a[parent]); child parent; parent (child - 1) / 2; } else//已经完成调整就退出 { break; } } }删除元素与向下调整算法void HpPop(HP* php) { assert(php); assert(php-size 0); Sawp(php-a[php-size - 1], php-a[0]); php-size--; AdjustDown(php-a, 0, php-size); }想要删除堆中的元素删除的是堆的根结点删除的方式就是将根节点与堆的最后一个叶子结点做交换此时堆中除了根节点的位置外其他的结点还是符合小根堆的所以我们需要重新从上往下的调整堆让堆变成重新有序与向上调整相似因为我们要创建的是小根堆所以当子孩子比该结点小的话就把他交换上来落实在代码上void AdjustDown(HeapDataType* a, int prent, int n) { int child prent * 2 1; while (child n) { if (child 1 n a[child 1] a[child])//先判断是否越界 { child; } if (a[child] a[prent]) { Sawp(a[child], a[prent]); prent child; child prent * 2 1; } else { break; } } }返回元素、判空、返回个数//返回元素 HeapDataType HpTop(HP* php) { assert(php); assert(php-size 0); return php-a[0]; } //判空 bool HpEmpty(HP* php) { assert(php); return php-size 0; } //返回元素个数 int HpSize(HP* php) { assert(php); return php-size; }这三个函数都非常简单就不多赘述了其实这整个模拟下来代码还是比较的简单的主要是加深了一下对堆的理解尤其是体现在向上、向下调整算法那里就体现了堆的核心思想完