江苏南京建设局官方网站,域名解析到别的网站,得物app订单制作,专业网站建设服务包括一、树的重要知识点 节点的度#xff1a;一个节点含有的子树的个数称为该节点的度#xff08;有几个孩子#xff09;叶节点或终端节点:度为0的节点称为叶节点#xff1b;如上图#xff1a;B、C、H、I...等节点为叶节点#xff08;0个孩子#xff09;非终端节点或分支节点…一、树的重要知识点 节点的度一个节点含有的子树的个数称为该节点的度有几个孩子叶节点或终端节点:度为0的节点称为叶节点如上图B、C、H、I...等节点为叶节点0个孩子非终端节点或分支节点度不为0的节点 如上图D、E、F、G...等节点为分支节点父节点若一个节点含有子节点则这个节点称为其子节点的父节点 上图A是B的父节点孩子节点或子节点一个节点含有的子树的根节点称为该节点的子节点 上图B是A的孩子节点兄弟节点具有相同父节点的节点互称为兄弟节点 如上图B、C是兄弟节点(亲兄弟)树的度一棵树中最大的节点的度称为树的度 如上图树的度为6最多有几个孩子节点的层次从根开始定义起根为第1层根的子节点为第2层以此类推树的高度或深度树中节点的最大层次 如上图树的高度为4H表示从1开始 堂兄弟节点双亲在同一层的节点互为堂兄弟如上图H、I互为兄弟节点节点的祖先从根到该节点所经分支上的所有节点如上图A是所有节点的祖先子孙以某节点为根的子树中任一节点都称为该节点的子孙。如上图所有节点都是A的子孙 森林由mm0棵互不相交的树的集合称为森林 二、二叉树 二叉树的度孩子最多为2可以是0、1、2只有一个孩子是左/右孩子均可上面是二叉树的所有可能组成部分。
1、完全二叉树满二叉树 满二叉树有h层且每层的结点都是满的。共 2^h-1个结点
完全二叉树有h层前h-1层满最后一层最少一个结点n的范围是 2^(h-1)n 2^h-1
2、二叉树的性质 几个公式
首先设孩子为0/1/2的结点总数分别为N0/N1/N2
可得 N0 N21 该等式恒成立。 N1的数量是不确定的。
但是对于满二叉树。N10, 观察一下图就知道了。
对于完全二叉树N1 0或1.
二叉树的深度H HlogN约等于所以从上到下遍历一遍的时间复杂度为OlogN
3、孩子与父亲的关系互相查找
假设将二叉树的结点从上到下从左到右从0开始标记结点的个数设孩子下标为child父亲的下标为parent则有以下关系
1、parent child-1/ 2 左右孩子均满足
2、左孩子 child 2*parent 1
3、右孩子 child 2*parent 2
同时如果结点总数为n此时把n看作是下标child必须n孩子结点才能存在即 0~n-1
三、堆的概念
1、二叉树的顺序存储结构 与链表类似堆这种数据结构也是分为物理结构和逻辑结构。
逻辑结构上是一棵完全二叉树物理结构上是顺序表。
上图中为普通二叉树的两种结构如果不是完全二叉树就会导致顺序表的空间浪费例如最下面一层如果只有最后一个结点存在那么顺序表的一半左右大小的空间就会被浪费而堆的产生就是为了解决这种空间浪费的。完全二叉树的结构使其能更好的利用顺序的空间。
2、堆的分类 分为 大根堆和小根堆两种即每个parent结点的val值的大小都要比其child结点的val大或小。
四、堆的接口函数
typedef int HPDatatype;typedef struct Heap
{HPDatatype* a;int capacity;int size;
}HP;//堆的初始化
void HPInit(HP* php);
//堆的销毁
void HPDestroy(HP* php);
//入数据
void HPPush(HP* php, HPDatatype x);
//删除数据
void HPPop(HP* php);
//判断堆是否为空
bool HPEmpty(HP* php);
//返回堆中元素个数
int HPSize(HP* php);
//返回堆顶元素
HPDatatype HPTop(HP* php);
//交换2个数据
void Swap(HPDatatype* p1, HPDatatype* p2);
//向下调整
void AdjustDown(HPDatatype* a, int parent, int size);
//向上调整
void AdjustUp(HPDatatype* a, int child);五、初始化
//堆的初始化
void HPInit(HP* php)
{assert(php);HPDatatype* tmp (HPDatatype*)malloc(sizeof(HPDatatype) * 4);if (NULL tmp){perror(malloc fail);return ;}php-a tmp;php-capacity 4;php-size 0;}堆的结构与顺序表类似都是一个指针指向物理存储的数组size表示现有数据的个数capacity表示当前的容量。
malloc一段空间给指针a然后调整size为0capacity初始化为4个元素的大小。
六、插入数据 先判断物理空间上的存储是否足够不够就增容。
在size位置插入数据后要对数据进行向上调整操作 向上调整的原因是为了维持堆的结构因为插入的数据的值的大小是不确定的如果不调整就会破坏堆的结构因此从第二个数据开始就要不断向上调整。
传入的参数为a指向的数组以及刚刚插入的要调整的数据的下标
七、向上调整函数 传入child下标通过parent (child-1)/2找到其父亲结点的下标位置因为这里以大根堆为例因此只要a[child]a[parent]就交换交换完后孩子变为原来的父亲父亲继续找他的父亲这样向上迭代直到child变为0即堆顶它就是堆中最大的元素了没有调整空间了。或者是不满足孩子大于父亲的条件直接跳出了。 交换函数
只是实现简单的两个元素的数据交换注意函数的返回值类型以及传入的是地址。 八、删除数据 一开始的size是删除前堆中元素的总数我这里先让size--使其指向被删除的那个元素然后交换堆顶元素和要删除的元素最后对堆顶的元素进行向下调整操作。
实现时可以改变顺序但是一定要保证前后逻辑的统一包括下面的向下调整函数的实现。
九、向下调整函数 这里的size接收的是pop函数中的size-1即现在的size为向下调整的数据范围共size个。
因为交换数据后最大的数据来到数组的最后位置我们只是通过size--来避免访问他并没有真正的将它删除因此原来在数组最后现在在堆顶的那个元素在向下调整时不能包含被删除的那个元素。
函数过程分析parent为向下调整的那个元素先通过 child parent*21找到它的左孩子进入循环后先判断一步找出左右孩子中较大的那个其中child1size是为了保证右孩子也在数组范围内如果不在就默认为左孩子大了。
找出较大的孩子后将其val值与parent比较如果大于parent就交换然后父亲变为孩子孩子继续向下迭代找他的孩子直到childsize超出数组范围。 十、返回个数、堆顶、销毁函数 这几个函数很简单与前面的几种数据结构相似这里不多陈述。
十一、测试结果 插入的结果为大堆。 由于删除后不会访问最后一个元素所以除了原来的最大值8外其它7个数字仍然满足大堆结构 通过循环 取出堆顶元素删除操作可以获取所有堆顶元素。 引入k变量可以取出k个堆顶元素又因为堆顶元素都是堆中最大或最小的因此可以解决后面的topk问题。
十二、函数实现具体代码
#includeHeap.h//堆的初始化
void HPInit(HP* php)
{assert(php);HPDatatype* tmp (HPDatatype*)malloc(sizeof(HPDatatype) * 4);if (NULL tmp){perror(malloc fail);return ;}php-a tmp;php-capacity 4;php-size 0;}//交换函数交换父子数据
void Swap(HPDatatype* p1, HPDatatype* p2)
{HPDatatype tmp *p1;*p1 *p2;*p2 tmp;}//向上调整任意传入一个下标对它及其祖先进行向上调整前提是左右子树都是 大/小堆
void AdjustUp(HPDatatype* a, int child)
{//chile 和 parent 都是下标的数字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 HPPush(HP* php, HPDatatype x)
{assert(php);//先判断是否需要增容如需要则增容if (php-size php-capacity){HPDatatype* tmp (HPDatatype*)realloc(php-a, sizeof(HPDatatype) * 2 * (php-capacity));if (NULL tmp){perror(realloc fail);return;}php-a tmp;php-capacity * 2;}//入数据 先插入到尾部即物理存储上数组的最后然后向上调整php-a[php-size] x;AdjustUp(php-a,php-size);php-size;}//判断堆是否为空
bool HPEmpty(HP* php)
{return php-size 0;
}//向下调整,前提是左右子树都是 大/小堆
void AdjustDown(HPDatatype* a, int parent,int size)
{int child parent * 2 1;while (child size)//叶结点为止叶节点没有孩子即child下标超过数组范围{//先找出来2个子节点中较大的那一个,因为parent的值要和较大的比较//此时如果交换值大的child变为parent满足比他的兄弟大if ((child1 size) a[child 1]a[child])//起始的child一定是左孩子,检查越界{child child 1;}//向下调整if (a[child] a[parent]){Swap(a[parent], a[child]);parent child;child child * 2 1;//每次都从左边的节点开始}else{break;}}}//删除数据 删除堆顶的元素才有意义根据大根堆和小根堆可以得到top为max或min
void HPPop(HP* php)
{assert(php);assert(!HPEmpty(php));//删完之后还要保证为堆的结构//如果只是简单的向前覆盖由于物理上是数组存储就会导致堆的父子结构被打乱, 无法通过下标关系找父/子//无法进行后续删除因此可以选择首尾元素交换删除尾部后堆顶元素向下调整php-size--;Swap(php-a[0], php-a[php-size]);AdjustDown(php-a, 0, php-size);}//返回堆中元素个数
int HPSize(HP* php)
{assert(php);return php-size;
}
//返回堆顶元素
HPDatatype HPTop(HP* php)
{assert(php);return php-a[0];
}//堆的销毁
void HPDestroy(HP* php)
{assert(php);php-capacity 0;php-size 0;free(php-a);
}//9 8 7 6 5 0 2 1 4 3 今天讲的是堆的概念及其主要函数的实现下一篇文章我将详细讲述堆的应用。如 堆排序、topk问题等感谢各位看到最后。
