4.堆_树（汇总版）-阿里云开发者社区

1.树概念及结构

1.1树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

有一个特殊的结点，称为根结点，根节点没有前驱结点
除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

因此，树是递归定义的。

【注意】：树形结构中，子树之间不能有交集，否则就不是树形结构

1.2 树的相关定义

节点的度：子树的个数
叶节点或终端节点：度为0的节点称为叶节点
分支节点：度不为0的节点
兄弟节点：具有相同父节点的节点
树的度：树最大的节点的度
节点的层次：根为第1层，根的子节点为第2层，以此类推
树的高度或深度：树中节点的最大层次；如上图：树的高度为4
堂兄弟节点：双亲在同一层的节点互为堂兄弟
祖先：从根到该节点所经分支上的所有节点
子孙：以某节点为根的子树中任一节点都称为该节点的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林；

根据上图，读懂这一段话就没问题啦，A的度是6，PQ是叶，DE是分支节点也是兄弟节点，树的度为6，A为第一层，树的高度为4，HI是堂兄弟结点，A是祖先，其余的都是子孙

重点理解度：结点连接的子树个数

1.3 树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的左孩子右兄弟表示法。

表示文件系统的目录树结构

2.二叉树概念及结构

2.1概念

一棵二叉树是结点的一个有限集合，可以帮其想象为一颗计划生育的树

1. 或者为空

2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成

3. 最大度为2

4. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

2.2现实中的二叉树

哈哈膜拜一下

2.3 特殊的二叉树

1. 满二叉树：如果每一个层的结点数都达到最大值。也就是说，如果一个二叉树的层数为K，且结点总数是 2^k-1，则它就是满二叉树。

2. 完全二叉树：完全二叉树是效率很高的数据结构，最后一层从左到右排，可以不排满。满二叉树是一种特殊的完全二叉树。长度为h的完全二叉树，节点数量的范围[ 2^(h-1) , 2^h-1]

2.4 二叉树的性质

1. 非空二叉树的第i层上最多有 2^(i-1) 个结点.

2. 深度为h的二叉树的最大结点数是2^h-1 .

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 , 度为2的分支结点个数为 ,则有n(0)＝n(2)＋1

以满二叉树理解, i 层(即度为0）是2^(i-1) , 以上（i-1）层（即度为2）有节点2^(i-1)-1

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h= . (log以2 为底，n+1为对数)

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，奇为左孩子，偶为右孩子，双亲为（i-1)/2

2.5 二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

1. 顺序结构，数组存储（完全二叉树适用）

2.链式结构，链表实现 (后面红黑树，会涉及到三叉链表)

模拟实现：

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

3.1 二叉树的顺序结构--堆

完全二叉树更适合使用顺序结构存储。通常把堆(一种二叉树)使用顺序结构的数组来存储

【区分】

二叉树堆：一种数据结构

虚拟进程地址空间中的堆：操作系统中管理内存的一块区域分段。

小堆头最小，大堆头最大

3.2 堆的实现

3.2.1打印

//打印
void HeapPrint(HP* php)
{
  assert(php);
  for (int i = 0; i < php->size; ++i)
  {
    printf("%d ", php->a[i]);
  }
  printf("\n");
}

3.2.2 堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

模拟实现如下：

//向下调整
void Adjustdown(HPDataType* a, int n, int parent)
{
  int child = parent * 2 + 1;
 
  while (child < n)
  {
    if (child + 1 < n && 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 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;
    }
 
  }
}

3.2.3 堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

void HeapCreate(Heap* hp, HPDataType* a, int n)
{
  assert(hp);
  assert(a);
 
  hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
  if (!hp->_a)
  {
    perror("malloc fail");
    exit(-1);
  }
 
  hp->_capacity = hp->_size = n;
 
  //将a中的元素全部转移到堆中
  memcpy(hp->_a, a, sizeof(HPDataType) * n);
 
  //从最后一位开始遍历调整
  for (int i = n; i >0; i--)
  {
    Adjustup(hp->_a, i);//按向上调整，此建立大堆
  }
 
}

建堆的时间复杂度为O(N)

3.2.4 堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

void HeapPush(Heap* hp, HPDataType x)
{
  assert(hp);
 
  if (hp->_capacity == hp->_size)//扩容
  {
    int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
    HPDataType* new = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
    if (!new)
    {
      perror("realloc fail");
      exit(-1);
    }
 
    hp->_a = new;
    hp->_capacity = newcapacity;
  }
 
  hp->_a[hp->_size++] = x;
 
  Adjustup(hp->_a, hp->_size - 1);
 
}

！！！3.2.5 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据交换，然后删除数组最后一个数据，再进行向下调整算法。

//删除堆顶
void HeapPop(Heap* hp)//先将最后一个数与堆顶交换，然后再让size--，再进行向下调整
{
  assert(hp);
 
  swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
  hp->_size--;
 
  Adjustdown(hp->_a, hp->_size, 0);
 
}

3.2.6 堆的代码实现

.h：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
#include<string.h>
 
typedef int HPDataType;
typedef struct Heap
{
  HPDataType* a;
  int size;
  int capacity;
}HP;
 
void AdjustDown(HPDataType* a, int n, int parent);
void AdjustUp(HPDataType* a, int child);
void Swap(HPDataType* p1, HPDataType* p2);
 
 
// 堆的构建
void HeapCreate(HP* hp, HPDataType* a, int n);
 
void HeapPrint(HP* php);
void HeapInit(HP* php);
void HeapDestroy(HP* php);
 
// 保持他继续是一个堆 O(logN)
void HeapPush(HP* php, HPDataType x);
 
// 删除堆顶的数据，并且保持他继续是一个堆 O(logN)
void HeapPop(HP* php);
 
HPDataType HeapTop(HP* php);
 
int HeapSize(HP* hp);
// 堆的判空
bool HeapEmpty(HP* hp);

heap .c:

#include"pile.h"
 
//交换的模拟实现
void swap(HPDataType* s1, HPDataType* s2)
{
  HPDataType temp = *s1;
  *s1 = *s2;
  *s2 = temp;
}
//向上调整
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 Adjustdown(HPDataType* a, int n, int parent)
{
  int child = parent * 2 + 1;
 
  while (child < n)
  {
    if (child + 1 < n && 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 HeapCreate(Heap* hp, HPDataType* a, int n)
{
  assert(hp);
  assert(a);
 
  hp->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);
  if (!hp->_a)
  {
    perror("malloc fail");
    exit(-1);
  }
 
  hp->_capacity = hp->_size = n;
 
  //将a中的元素全部转移到堆中
  memcpy(hp->_a, a, sizeof(HPDataType) * n);
 
  //建堆
  for (int i = 1; i < n; i++)
  {
    Adjustup(hp->_a, i);//按向上调整，此建立大堆
  }
 
}
 
void HeapDestory(Heap* hp)
{
  assert(hp);
  free(hp->_a);
  hp->_a = NULL;
 
  hp->_capacity = hp->_size = 0;
}
 
void HeapPush(Heap* hp, HPDataType x)
{
  assert(hp);
 
  if (hp->_capacity == hp->_size)//扩容
  {
    int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
    HPDataType* new = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
    if (!new)
    {
      perror("realloc fail");
      exit(-1);
    }
 
    hp->_a = new;
    hp->_capacity = newcapacity;
  }
 
  hp->_a[hp->_size++] = x;
 
  Adjustup(hp->_a, hp->_size - 1);
 
}
//删除堆顶
void HeapPop(Heap* hp)//先将最后一个数与堆顶交换，然后再让size--，再进行向下调整
{
  assert(hp);
 
  swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
  hp->_size--;
 
  Adjustdown(hp->_a, hp->_size, 0);
 
}
 
HPDataType HeapTop(Heap* hp)//取堆顶
{
  assert(hp);
  assert(hp->_size > 0);
 
  return hp->_a[0];
}
 
int HeapSize(Heap* hp)//堆大小
{
  assert(hp);
 
  return hp->_size;
}
 
int HeapEmpty(Heap* hp)//判堆空
{
  assert(hp);
 
  return hp->_size == 0;
}

test.c

#include"pile.h"
 
 
void test()
{
  Heap hp;//创建一个堆
  int arr[] = { 1,6,2,3,4,7,5 };
  HeapCreate(&hp, arr, sizeof(arr) / sizeof(arr[0]));
  //HeapPush(&hp, 10);
  printf("%d\n", HeapSize(&hp));
  while (!HeapEmpty(&hp))
  {
    printf("%d %d \n", HeapTop(&hp), HeapSize(&hp));
    HeapPop(&hp);
  }
 
  printf("%d\n", HeapSize(&hp));
  HeapDestory(&hp);
  
  HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
 
  printf("\n");
}
 
int main()
{
  test();
  return 0;
}

4.堆_树（汇总版）