【数据结构】堆与二叉树

一、树的概念 1.1 什么是树？

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

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

根节点的特色是他没有前驱节点，除了根节点之外的其他节点被分成了 M 个 ( M > 0 ) 互不相交的集合 T 1 、 T 2 、 . . . T m {T_1}、T_2、...T_m T1​、T2​、...Tm​

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

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

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 概念

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

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

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

二叉树的不同情况 注意：树可以没有节点，此时就是空树

2-2 特殊二叉树

满二叉树 （ 图 a ）

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

完全二叉树 （图 b ）

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

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

2-3 二叉树的性质

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

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

对任何一棵二叉树, 如果度为 0 其叶节点个数为 n 0 {n_0} n0​ , 度为 2 的分支节点个数为 n 2 {n_2} n2​ ,则有 n 0 = n 2 + 1 {n_0 = n_2 + 1} n0​=n2​+1

若规定根节点的层数为1，具有 n 个节点的满二叉树的深度， h = l o g 2 ( n + 1 ) {h = log_2(n+1)} h=log2​(n+1)

注意这里的 log 是以2为底

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

于序号为 i。的节点有

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

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

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

2-4 二叉树的存储结构

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

顺序存储结构

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

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

链式存储结构

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

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

三、堆 （ Heap ) 3.1 堆的概念

堆就是将数据以二叉树的顺序存储结构进行实现 且满足 K i < = K 2 ∗ i + 1 {K_i <= K_{2*i+1}} Ki​<=K2∗i+1​ 且 K i < = K 2 ∗ i + 2 {K_i <= K_{2*i+2}} Ki​<=K2∗i+2​ （称为小堆） 或 K i > = K 2 ∗ i + 1 {K_i >= K_{2*i+1}} Ki​>=K2∗i+1​ 且 K i > = K 2 ∗ i + 2 {K_i >= K_{2*i+2}} Ki​>=K2∗i+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 堆的分析 堆的时间复杂度：O( n ) – 利用错位相减法可以得到堆的空间复杂度：取决于malloc的大小 （ 通常是O(n) ） 3.4 堆的应用

堆排序

堆排序的两个步骤

建堆

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

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

代码实现

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; } }

Top-K 问题

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

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

建堆

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

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

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

注意替换后如果不满足堆的特性，要进行调整 四、二叉树 （ BinaryTree )

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

4.1 回顾

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

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

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

4.2 二叉树的遍历

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

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

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

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

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

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; } // 整个二叉树都没有找到就返回NULL return NULL; } 4.3.6 层序遍历 & 判断一棵树是否是完全二叉树

层序遍历

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

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

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

队列的特性：先进先出

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

先 Push 根节点进栈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; }