【数据结构】堆与二叉树

一、树的概念

1.1 什么是树？

树是一种非线性的数据结构，其由 n 个 ( n >= 0 ) 有限节点所组成的一个有层次关系的集合。之所以称其为树，是因为其逻辑结构看起来像是一颗倒挂的树。

在树中，有一个特殊的节点称为根节点（如上图中的 body 节点）

根节点的特色是他没有前驱节点，除了根节点之外的其他节点被分成了 M 个 ( M > 0 ) 互不相交的集合 $T_1、T_2、...T_m$

每一个集合的结构与树类似，我们又称其为子树，每个子树的根节点都有且只有一个前驱节点

我们从图中可以看到树的逻辑结构是一层一层递下去的，因此，树是以递归来实现。

1.2 与树相关的专有名词

节点的度：一个节点的子树个数

​ 以上图为例：body 节点的度为 3 （ul、p、div）

叶节点或终端节点：度为零的节点

​ 以上图为例： li、li、p、img 都是叶节点

分支节点或非终端节点：度不为零的节点

​ 以上图为例：body、ul、div 都是分支节点

双亲节点或父节点：如果一个节点有子节点，则这个节点就是这个子节点的双亲节点

​ 以上图为例：body节点是 ul、p、div 的双亲节点

孩子节点或子节点：一个节点所拥有的子树根节点就是这个节点的孩子节点

​ 以上图为例：body节点的孩子节点为 ul、p、div

兄弟节点：有相同双亲节点的节点

​ 以上图为例：ul的兄弟节点是p和div；li的兄弟节点是li和img

树的度：最大节点的的度就是树的度

​ 以上图为例：最大节点的度是3 （body节点）所以树的度为3

节点的层次：以根节点开始，根为第一层，根节点的子节点为第二层，以此类推

树的高度：就是节点的最大的层次

​ 以上图为例：最大的节点层次是3，所以树的高度是3

堂兄弟节点：双亲在同一层的节点互为堂兄弟

​ 以上图为例 li 和 img 是堂兄弟节点

节点的祖先：从根到该节点所经分支上的所有节点

​ 以上图为例：body是所有节点的祖先

子孙：以某节点为根的子树中任一节点都称为该节点的子孙

​ 以上图为例：除了body节点以外的节点都是body节点的子孙

森林：由 m（m>0）棵互不相交的树的集合称为森林

二、二叉树的概念

2.1 概念

二叉树的本质就是树，但二叉树有着自己的特殊性质

从图中可以看到两个二叉树的性质

1. 二叉树每个节点的度不会大于2
2. 二叉树有左右子树之分

二叉树的不同情况

注意：树可以没有节点，此时就是空树

2-2 特殊二叉树

1. 满二叉树 （ 图 a ）

   一个二叉树每一层的节点数都是该层的最大值，则这个二叉树就是满二叉树

2. 完全二叉树 （图 b ）

   一个二叉树每一层的节点依照从左至右的顺序，如果有一层的节点不是该层的最大值，则这个二叉树是完全二叉树

   注意：满二叉树是一个特殊的完全二叉树
   

2-3 二叉树的性质

1. 若根节点的层数为1，则第 i 层的最大节点数为 $2^{i-1}$

2. 若根节点的层数为1，则深度为 h 的二叉树最大节点数为 $2^h-1$

3. 对任何一棵二叉树, 如果度为 0 其叶节点个数为 $n_0$ , 度为 2 的分支节点个数为 $n_2$ ,则有 $n_0=n_2+1$

4. 若规定根节点的层数为1，具有 n 个节点的满二叉树的深度，$h=lo{g}_2(n+1)$

   注意这里的 log 是以2为底

5. 对于具有 n 个节点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对

   于序号为 i。的节点有

   （1）若 i > 0，i 位置节点的双亲序号：$\frac{i-1}{2}$； i=0，i 为根节点编号，无双亲节点

   （2）若 2i+1< n，左孩子序号：2i+1，2i+1 >= n 则无左孩子

   （3）若 2i+2 <n，右孩子序号：2i+2，2i+2 >= n 则无右孩子

2-4 二叉树的存储结构

一般来所，二叉树的存储结构可以分成两种

1. 顺序存储结构

   顺序存储结构就是利用数组来实现，通常只有完全二叉树才会使用数组来实现，因为如果不是完全二叉树会有空间浪费的问题，在实际当中只有堆会使用到二叉树的顺序存储结构

   虽然物理结构上是数组，但是逻辑结构上还是一棵二叉树
   

2. 链式存储结构

   链式存储结构就是以链表来表示一棵二叉树，在目前主要以二叉链表来表示，每个节点由数据域（data）、左指针（指向左孩子 – leftchild）、右指针（ 指向右孩子 – rightchild）所组成

   而二叉树的延伸 – 红黑树则以三叉链表来表示，在二叉链表的基础上再加上指向双亲节点的指针
   
   在这里我们主要介绍一般的二叉树

三、堆 （ Heap )

3.1 堆的概念

堆就是将数据以二叉树的顺序存储结构进行实现
且满足 $K_i<=K_{2\ast i+1}$ 且 $K_i<=K_{2\ast i+2}$ （称为小堆）
或 $K_i>=K_{2\ast i+1}$ 且 $K_i>=K_{2\ast i+2}$ （称为大堆）

堆的性质

1. 堆中某个节点的值总是不大于或不小于其父节点的值 （满足大堆或小堆 ）

2. 堆总是一棵完全二叉树
   

3.2 堆的接口

// 以順序表實現堆
typedef int HeapDatatype;
typedef struct Heap
{HeapDatatype *a; // 用來創建數組int capacity;    // 容量int size;        // 有效數據個數
} HP;
// 初始化
void HeapInit(HP *php);
// 初始化數組（利用一个已存在的数组来建堆）
void HeapInitArray(HP *php, int *a, int n);
// 交換
void Swap(HeapDatatype *x1, HeapDatatype *x2);
// 向上調整
void AdjustUp(HeapDatatype *a, int child);
// 向下調整
void AdjustDown(HeapDatatype *a, int n, int parent);
// 插入數據
void HeapPush(HP *php, HeapDatatype x);
// 刪除數據
void HeapPop(HP *php);
// 取堆頂數據
HeapDatatype HeapTop(HP *php);
// 判斷堆是否為空
bool HeapEmpty(HP *php);
// 堆有效數據的個數
int HeapSize(HP *php);
// 堆銷毀
void HeapDestroy(HP *php);

3.2.1 堆初始化

void HeapInit(HP *php){assert(php);php->a = (HeapDatatype*)malloc(sizeof(HeapDatatype)*4);if(php->a == NULL){perror("malloc fail");return;}php->capacity = 4;php->size = 0;
}

3.2.2 堆初始化（以另一个数组来为堆做初始化）

void HeapInitArray(HP * php,int *a,int n){assert(php);php->a = (HeapDatatype*)malloc(sizeof(HeapDatatype)*n);if(php->a == NULL){perror("malloc fail");return;}php->capacity = n;php->size = n;for(int i = 0;i<n;++i){php->a[i] = a[i];}// 建堆for(int i = (i-2)/2; i >= 0; --i ){AdjustDown(php->a,php->size,i);}  
}

3.2.3 向上调整

void AdjustUp(HeapDatatype*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.4 向下调整

void AdjustDown(HeapDatatype*a, int n, int parent){int child = 2*parent + 1;// 判断那个孩子比较大while(child < n){if(child + 1 < n && a[child] < a[child+1]){child++;}if(a[child] > a[parent] ){Swap(&a[child],&a[parent]);parent = child;child = 2*parent+1;}else{break;}}
}

3.2.5 插入数据

void HeapPush(HP *php, HeapDatatype x){assert(php);if(php->capacity == php->size){HeapDatatype* tmp = (HeapDatatype*)realloc(php->a,sizeof(HeapDatatype)*2*php->capacity);if(tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size++] = x;// 插入之后，要确保依然满足堆的特性，所以要进行向上调整AdjustUp(php->a,php->size-1);
}

3.2.6 删除数据

删除数据的思路

代码实现

void HeapPop(HP * php){assert(php);Swap(&php->a[0],&php->a[size-1]);php->size--;AdjustDown(php->a,php->size,0);
}

3.2.7 取堆顶的数据

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

3.2.8 判断堆是否为空

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

3.2.9 取堆中有效数据个数

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

3.2.10 堆的销毁

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

3.3 堆的分析

1. 堆的时间复杂度：O( n ) – 利用错位相减法可以得到
2. 堆的空间复杂度：取决于malloc的大小 （ 通常是O(n) ）

3.4 堆的应用

1. 堆排序

   堆排序的两个步骤

   1. 建堆

      • 如果要排升序 – 建大堆
      • 如果要排降序 – 建小堆

   2. 利用堆删除的思想来完成堆排序

   代码实现

   void HeapSort(int *a, int n){ // n 是有效数据个数// 先建堆（假设我们要排升序）for(int i = 0;i<n;++i){AdjustDown(a,i);}// 升序while(n >= 0){Swap(&a[0],&a[n-1]); // 因为是排升序（建大堆）所以堆顶的数据一定是最大的AdjustDown(a,n,0);--n;}
   }
   

2. Top-K 问题

   排完序后（这里要排降序），我们就可以取得最大的前 k 个数据

   但如果数据量大的话，直接排序就不是那么好的方法，因此，我们可以采用以下方法

   1. 建堆

      • 求前 k 个最大的数据 – 建大堆

      • 求前 k 个最小的数据 – 建小堆

   2. 用剩余的 N-K 个元素依次与堆顶元素来比较，不满足则替换堆顶元素，将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素

   • 注意替换后如果不满足堆的特性，要进行调整

四、二叉树 （ BinaryTree )

要说明二叉树，我们需要先建一个二叉树，注意当前的创建方法并不是二叉树的真正创建方法，真正的创建方法会在未来更进阶的二叉树中进行说明，当前主要以快速上手二叉树为主

4.1 回顾

我们前面有说到，二叉树是

1. 空树
2. 非空：由根节点、根节点的左子树、根节点的右子树组成

从二叉树的逻辑结构不难发现二叉树的实现是以递归来实现的
而对二叉树的增删查改通常不是通过一般的二叉树实现的，所以在这里我们不讨论二叉树的增删查改，我们会利用二叉树的遍历来了解最一般的二叉树

4.2 二叉树的遍历

二叉树的遍历主要问题有四种

1. 前序遍历：访问顺序 – 根 - 左子树 - 右子树

2. 中序遍历：访问顺序 – 左子树 - 根 - 右子树

3. 后序遍历：访问顺序 – 左子树 - 右子树 - 根

4. 层序遍历：访问顺序 – 依序访问每一层的节点，一层访问完后再访问下一层
   
   层序遍历不仅遍历方式和其他三种不一样，实现方式也与其他三种不一样

4.3 二叉树的遍历（代码实现）

4.3.1 创建节点

因为我们不是以正规的二叉树创建方法实现，所以我们要自己创建二叉树

// 先定义结构体
typedef int BTDatatype;
typedef struct BinaryTreeNode{BTDatatype data; // 存储数据struct BinaryTreeNode* left; // 指向左孩子struct BinaryTreeNode* right; // 指向右孩子
}BTNode;
// 创建节点
BTNode* CreateNode(BTDatatype x){BTNode* node = (BTNode*)malloc(sizeof(BTNode));if(node == NULL){perror("malloc fail");return;}node->data = x;node->left = NULL:node->right = NULL:return node;
}

4.3.2 创建树

创建节点并创建树

BTNode* CreateTree(){// 创建节点BTNode* node1 = CreateNode(1);BTNode* node2 = CreateNode(2);BTNode* node3 = CreateNode(3);BTNode* node4 = CreateNode(4);BTNode* node5 = CreateNode(5);BTNode* node6 = CreateNode(6);node1->left = node2;node1->right = node3;node2->left = node4;node2->right = node5;node3->right = node6; // 这里没有写错，我们让node3没有左孩子return node1;
}

4.3.3 二叉树遍历

// 前序遍历 (我们会把空节点一起打印出来)
void PreOrder(BTNode* root){if(root == NULL){printf("NULL ");return;}// 前序遍历的访问顺序 -- 根 - 左子树 - 右子树// 先访问根printf("%d ",root->data);// 访问左子树PreOrder(root->left);// 访问右子树PreOrder(root->right);
}

// 中序遍历
void InOrder(BTNode* root){if(root == NULL){printf("NULL ");return;}// 中序遍历的访问顺序 -- 左子树 - 根 - 右子树// 左子树InOrder(root->left);// 根printf("%d ",root->data);// 右子树InOrder(root->right);
}

//后序遍历
void PostOrder(BTNode* root){if(root == NULL){printf("NULL ");return;}// 后序遍历的访问顺序 -- 左子树 - 右子树 - 根PostOrder(root->left);PostOrder(root->right);printf("%D ",root->data);
}

4.3.4 二叉树的其他接口

// 求二叉树的节点数
// 方法：求得左子树和右子树的节点数后再加1（根节点）
int TreeSize(BTNode* root){if(root == NULL){return;}int lnum = TreeSize(root->left);int rnum = TreeSize(root->right);return lnum + rnum + 1;
}
// 求二叉树的高度
int TreeHeight(BTNode* root){if(root == NULL){return 0;}int lnum = TreeHeight(root->left);int rnum = TreeHeight(root->right);return lnum > rnum ? lnum + 1 : rnum + 1;
}

4.3.4 第k層的節點數

int TreeKLevel(BTNode* root, int k){if(root == NULL){return 0;}if(k == 1){return 1;}int lnum = TreeKLevel(root->left,k-1);int rnum = TreeKLevel(root->right,k-1);return lnum + rnum;
}

4.3.5 寻找值为x的节点（如果有多个值为x的节点则返回第一个节点）

// 思路：先从根节点开始，如果根节点的值不满足我们要找的，就找左子树的节点，如果左子树没有，找右子树的节点
BTNode* BinaryTreeFind(BTNode* root, BTDatatype x){if(root == NULL){return NULL;}if(root->data == x){return root;}// 将左子树的结果保存BTNode* lret = BTNBinaryTreeFind(root->left,x);if(lret){return lret;}// 将右子树的结果保存BTNode* rret = BinaryTreeFind(root->right,x);if(rret){return rret;}// 整个二叉树都没有找到就返回NULLreturn NULL;
}

4.3.6 层序遍历 & 判断一棵树是否是完全二叉树

层序遍历

我们前面有说过，层序遍历的实现和前、中、后序遍历有些不同，在实现层序遍历我们需要用到队列

栈与队列 — 关于队列的代码实现都在这篇博客中，但要注意在二叉树这里的队列的数据类型是BTNode*

如何以队列实现层序遍历？

队列的特性：先进先出

所以用队列实现层序遍历的步骤

1. 先 Push 根节点进栈
2. Pop 队头节点的时候将该节点的左右孩子 Push 到队列中

重要！因为判断是否是完全二叉树也会用到这个概念

// 层序遍历
void LevelOrder(BTNode* root){Queue q;QueueInit(&q);// 如果root不是空，就将根节点Push进队列if(root != NULL){QueuePush(&q,root);}// 当队列不为空时while(!QueueEmpty(&q)){BTNode* front = Queuefornt(&q); // 将对头的节点取出// 打印Printf("%d ", front->data);// 将对头节点的左右孩子 Push 进队列if(root->left){QueuePush(&q,root->left);}if(root->right){QueuePush(&q,root->right);}// 删掉对头的节点QueuePop(&q);}// 结束后要记得销毁队列QueueDestroy(&q);
}

判断一棵树是否是完全二叉树

我们前面说过完全二叉树有一个特性：每一层的节点是依序从左至右的

也就是说我们利用层序遍历的概念，只要空的节点后面存在非空节点，则这棵树就不是完全二叉树

bool BinaryTreeComplete(BTNode* root){Queue q;QueueInit(&q);if(root != NULL){QueuePush(&q,root);}while(!QueueEmpty(&q)){BTNode* front = Queuefront(&q);if(front == NULL){break;}QueuePush(&q,root->left);QueuePush(&q,root->right);QueuePop(&q);}// 第二次循环来判断后面有没有非空while(!QueueEmpty(&q)){BTNode* front = Queuefront(&q);if(front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}