速通数据结构与算法第六站树堆

系列文章目录

速通数据结构与算法系列

1   速通数据结构与算法第一站复杂度          http://t.csdnimg.cn/sxEGF

2   速通数据结构与算法第二站顺序表         http://t.csdnimg.cn/WVyDb

3   速通数据结构与算法第三站单链表          http://t.csdnimg.cn/cDpcC

4   速通数据结构与算法第四站双链表          http://t.csdnimg.cn/0VyDl

5   速通数据结构与算法第五站栈&&队列     http://t.csdnimg.cn/MRU83

感谢佬们支持！

系列文章目录

前言
一、树
1 树的概念
2 树的相关概念
3 树的表示方式
二、二叉树
1 概念
2 特殊的二叉树
3 二叉树的性质
4 二叉树的存储结构
三、堆
1 堆的概念结构
2 堆的实现
3 堆排序
4 堆的应用--Topk问题
四、链式二叉树
1 结构体
2 三种遍历方式
3 计算节点个数
4 计算深度
5 第k层的节点个数
6 相同的树
7 单值二叉树
8 二叉树查找值为x的节点
9 对称二叉树
10 层序遍历
11判断一棵树是否为完全二叉树
12 另一棵树的子树
补充概念：DFS、BFS
总结

前言

上篇博客我们学了简单的栈和队列，这次我们来学学不太容易的树和堆，大家要做好狠狠递归的准备哦~。树的学习实际上前期还不那么重要，重要的是后期的AVL和红黑树，但是有很多考验分治

和递归的关于树的OJ题。

一、树

1 树的概念

有关于树的定义，树是一种非线性的结构，它是由n（n>=0）个有限节点组成的一个具有层次关系的集合，它很像一颗倒挂的树，即跟在上而叶朝下的树

其中，最上面的节点称为根节点

除根结点外，其余节点被分成M（M>0）个互不相等的集合T1、T2……Tm，其中每个集合Ti（1<=i<M)又是一颗结构与数相同的子树。

所以说，树是递归定义的

(如下图所示)

注意：子树之间不能相交，否则就不能叫树，而是叫图（关于图我们将在速通数据结构高阶中学习~）

2 树的相关概念

树的相关概念有一大堆，我们来看一下~（以上图为例）

节点的度：一个节点包含子树的个数称为该节点的度；如：A的度为6

叶子节点/终端节点：度为0的节点；如上图的B、C、H、I等

非终端节点/分支节点：度不为0的节点；如上图的D、E等

双亲节点/父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；

如上图A为B的父节点

孩子节点/子节点：一个节点含有子树的根节点称为该节点的子节点；如上图，B是A的孩子节

点

兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B,C是兄弟节点

树的度：一棵树中，最大的节点的度称为树的度；如上图，树的度为6

节点的层次：从跟开始定义起，根所在的为第一层，根的子节点为第二层，以此类推

树的高度/深度：树中节点的最大层次；如上图，树的高度为4

堂兄弟节点：双亲在同一层的节点互称为堂兄弟；如上图，H,I互为堂兄弟节点

节点的祖先：从根到该根节点所经分支上的节点；如上图，A是所有节点的祖先

子孙：以某节点为根的子树中任一节点都为该节点的子孙；如上图，所有节点是A的子孙

森林：由m（m>0）棵互不相交的子树的集合称为森林（也就是之后我们要学的并查集）

3 树的表示方式

如何表示树也是一个值得思考的问题

1 假设我们已知树的度为5，我们可以这样表示

struct TreeNode
{int data;struct TreeNode* sub[5];
};

2 如果我们不知道树的度，那只能给一个顺序表而非静态的结构体数组

struct TreeNode
{int data;//struct TreeNode* sub[5];Seqlist q;
};

显然，这样开销太大了，由此我们有了下面的方法

3 用一个结构数组存储，每个结构存数据及父母的下标

struct TreeNode
{int data;int parent;
};

就像下图这样

但是这样也差点意思，我们引出最后一种牛逼的方法

4 左孩子右兄弟法

两个指针left、right；left只指向左孩子，而right只指向右边第一个兄弟

typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

二、二叉树

1 概念

二叉树就是度小于等于二的树。一棵二叉树有三部分组成：根，左子树，右子树

如图所示

当然，这其中也有一些特殊情况。有的树是空树，有的树只有根节点，有的树只有左子树，有的树只有右子树；这都属于二叉树

2 特殊的二叉树

满二叉树：一个二叉树，如果每一层节点数都达到最大值，那么就是满二叉树。也就是说

suppose一个二叉树有k层，如果他节点个数为2^k -1，那么就为满二叉树

完全二叉树：完全二叉树的前k-1层是满的，而最后一层要求从左到右连续

完全二叉树是效率很高的数据结构，后面的AVL,RBTree每次增删操作都是

在尽可能向完全二叉树靠拢；显然，满二叉树为一种特殊的完全二叉树

放一波图~

3 二叉树的性质

二叉树有一些乱七八糟的性质，而这些性质最喜欢在选择题里考，大家可以边画图边做理解

1 若规定根节点层数为1，则一颗非空二叉树的第i层上最多也2^(i-1)个节点

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

3 对任意一颗二叉树，如果度为0的叶子节点个数为n0，度为2的节点个数为n2，则有

n0=n2+1

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

5 对于具有n个节点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点

从0开始编号，，则对于序号为i的节点有

1 若i>0 i位置的双亲序号：（i-1）/2 if（i==0） i为根节点，无双亲节点

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

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

4 二叉树的存储结构

二叉树的存储也分顺序存储和链式存储两种

1 顺序存储

顺序存储就是数组，显然，这种存储方式一般只适合表示完全二叉树，因为别的二叉树中间可能会有空节点，造成空间的浪费。而下一个标题我们要学的堆就是顺序存储

（如图所示）

2 链式存储

二叉树的链式存储是指用类似链表的方法来表示一棵二叉树。

常见的方法是3个成员的二叉链表和4个成员的三叉链表

二叉链表只存值和左右孩子，三叉链表在此基础上存了父节点

（双叉链）

（三叉链）

三、堆

堆的概念结构

二叉树的顺序存储的一个应用就是堆

如果对K={k0,k1,k2……kn-1}，把他所有元素按照完全二叉树的顺序存储方式存在一个一维顺序表中，并满足Ki<=K2*i+1且Ki<=K2*i+2,则称为大堆，反之，称为小堆。

将根节点最大的堆称为最大堆（大根堆），根节点最小的堆称为最小堆（小根堆）

对应于STL为priority_queue，只需控制比较的仿函数即可适配出最大、最小堆

堆的性质

1 堆中的某个节点的值总是不大于/不小于其父节点的值

2 堆是一颗完全二叉树

堆的应用

1 堆可以排序

2 堆可以解决Topk问题

以大根堆为例，我们来看看它的逻辑结构和物理结构

如果我们要插入一个20，那就会是这样的

（显然是符合要求的，我们只需和父节点30比较即可得出）

再插一个60呢？

显然，这会影响部分祖先，所以我们要向上调整。

简单来说就是将60向上交换，直到它小于父节点为止。

显然可知，我们最多只需swap高度次（lgN），即最多交换至根即可，我们称这个过程为向上调整

多的不说，我们迅速写一波代码

堆的实现

先搞3个文件，heap.h,heap.c,test.c

简单看一下我们要介绍的接口：heap.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HPDataType;//大堆
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//初始化
void HeapInit(HP*hp);//销毁
void HeapDestroy(HP* hp);//push
void HeapPush(HP* hp, HPDataType x);//pop
void HeapPop(HP* hp);//empty
bool HeapEmpty(HP* hp);//size
int HeapSize(HP* hp);//堆顶
HPDataType HeapTop(HP* hp);//向上调整
void AdjustUp(HPDataType* a,int child);//向下调整
void AdjustDown(HPDataType* a,int n,int parent);

我们先简单写一下初始化和销毁，由于是适配器，所以其实就和写顺序表差不多的

// 初始化
void HeapInit(HP* hp)
{assert(hp);hp->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);if (hp->a == NULL){perror("malloc fail");exit(-1);}hp->size = 0;hp->capacity = 4;
}//销毁
void HeapDestroy(HP* hp)
{assert(hp);free(hp->a);hp->a = NULL;hp->capacity = hp->size = 0;
}

由于我们要进行很多交换操作，所以单独封装一个swap出来

//swap
void swap(HPDataType* px, HPDataType* py)
{HPDataType tmp = *px;*px = *py;*py = tmp;
}

重头戏在插入上，在上面的例子中我们知道，插入之后可能是要进行向上调整操作的

所以在push的逻辑中我们最后要调用向上调整

void HeapPush(HP* hp, HPDataType x)
{assert(hp);if (hp->size == hp->capacity){//扩容HPDataType tmp = (HPDataType*)realloc(hp->a, sizeof(HPDataType)*hp->capacity*2);if (tmp == NULL){perror("reolloc");exit(-2);}hp->capacity *= 2;hp->a = tmp;}hp->a[hp->size++] = x;//向上调整AdjustUp(hp->a, hp->size - 1);
}

下来就看如何实现向上调整了

其实逻辑还是很简单的，我们只需每次算出父节点的位置，和当前值进行比较，如果当前值更大，就进行swap，直到调整到根为止

代码如下~

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

堆排序

例：

{2，1，5，7，6，8，0，4，3，9}

堆排序，我们首先要有一个堆，所以可以对数组原地建堆

假设我们要排升序，那是建大堆/小堆？

如果按照依次取最小的数来排序的话，应该来建小堆。

这个时候问题来了，第一个数取到了，剩下的一堆数就不满足堆的性质了

所以我们应该建大堆

每次拿最大的数，拿的时候和最后一个数swap，这样最后一个数就会到第一个。

此时剩下的数仍然是一个最大堆

再让堆顶其向下调整即可，最后一个数的位置就好了

还有一个要考虑的事情就是如何建堆

最简单的就是从第二个数开始向上调整，一直调整到最后一个数，这称为向下调整建堆

还有一种是向下调整法

由于叶子节点没有孩子，显然不用向下调整

所以向下调整应该从最后一个非叶子节点开始，一直调到根

显然，向下调整建堆(O(N))的时间复杂度优于向上调整（O（N^2lgN））

毕竟一颗二叉树最后一层的节点数可能占总结点的一半呢

代码如下~

//swap
void swap(int* px, int* py)
{int tmp = *px;*px = *py;*py = tmp;
}//排升序--建大堆(向上调整建堆)
void HeapSort1(int* a, int n)
{for (int i = 1; i < n; ++i)//O(lgN){AdjustUp(a, i);}int end = n - 1;while(end>0){swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}//排升序--建大堆(向下调整建堆)
void HeapSort2(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}

堆的应用--Topk问题

Topk问题：即求数据集合中前k个最大/最小的元素，一般数据总量较大

比如：专业前10，世界500强，富豪榜等等

对于Topk问题，最简单的方式当然是排序，但是数据量大的话，无法一次全加载到内存中

，（当然归并排序是可以外排序的）用数据库又太麻烦，最简单的就是用堆排序

思路如下：

1 用数据集合的前k个建堆

前k个最大元素，则建小堆

前k个最小元素，则建大堆

2 用剩下的N-k个元素一次比较，如果大于/小于堆顶就入堆

这里列了一道题，大家可以试一试

（但其实涉及到了双关键字排序，在学C++可能不是特别好操作）

. - 力扣（LeetCode）

class Solution 
{
public:struct Greater{bool operator()(const pair<string,int>&p1,const pair<string,int>&p2){return p1.second>p2.second;}};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> m;for(auto &e:words){m[e]++;}vector<pair<string,int>> res(m.begin(),m.end());vector<string> ret;stable_sort(res.begin(),res.end(),Greater());for(int i=0;i<k;++i){ret.push_back(res[i].first);}return ret;}
};

四、链式二叉树

显然，如果随意来一个二叉树，就不适合用数组存储了

1 结构体

struct TreeNode {int val;struct TreeNode* left;struct TreeNode* right;};

2 三种遍历方式

三种遍历方式对应为前序、中序、后序

分别对应"根左右","左根右"，"左右根"的顺序

（值得注意的是，在多叉树中只有前序、中序两种遍历方式）

我们给到一颗二叉树

从根节点分为根，左子树，右子树

我们对上面的左子树，右子树也可以做同样的操作，直到一棵树的左右子树均为空，表示这棵树已经到叶子了。

针对递归类问题，我们要有这样的解题思路

1 先找到相同的子问题。（关注函数头是如何设计的）

2 只关心某一个子问题是如何解决的。（函数体如何设计？）

3 注意一下递归函数出口+返回值用不用接收？

以前序遍历为例

相同的子问题就是遍历根，再遍历根的左，再遍历根的右

所以我们只用传一个根即可，返回值设为void即可

    void preorder(TreeNode* root)

函数体可以这么设计

if(root==nullptr)
{return ;
}
cout<<root->val<<" ";//根左右_preorder(root->left);_preorder(root->right);

同理，根据访问根时机的不同，我们可以写出中序、后序

中序

void inorder(TreeNode*root)
{if(root==nullptr){return ;}inorder(root->left);cout<<root->val<<" ";inorder(root->right);
}

后序

void postorder(TreeNode* root){if (root == nullptr)return;//左右根postorder(root->left);postorder(root->right);cout<<root->val<<" ";        }

二叉树遍历还是很简单的，关键一点是我们要学到递归类问题的解决思路。

等后面深搜暴搜剪枝的时候就难了。

当然，三种递归方式也是可以用非递归实现的，我们需要用到栈这个我们就放到C++啦~

链式二叉树的学习会涉及到大量的递归，下面给大家放一些算法题叭~

类似二叉树的题一般都是通过递归做的，非递归就太麻烦了。

后期更深入的就是深搜，全排列，剪枝等等了

3 计算节点个数

. - 力扣（LeetCode）

递归出口：

显然，当我们遍历到空，就没有节点了

相同子问题：

每次遍历我们需要计算根的节点个数（1个）和他下面的左、右子树的节点个数

由于我们要算的是总共的个数，所以每一层的结果我们都要记录下来

我们直接加起来即可

我们可以直接写一个3目运算符

int countNodes(struct TreeNode* root)
{return root == NULL ? 0 : countNodes(root->left) + countNodes(root->right) + 1;
}

4 计算深度

. - 力扣（LeetCode）

计算深度也很简单

函数的的递归出口：

递归出口同样是遍历到空之后就不用走了

计算深度就是一直往最深的那层走，所以我们每次都要去找左、右子树中大的那个走

所以相同的子函数

每次选左右子树中较大的那个，并加上根的高度(1)

 int calculateDepth(TreeNode* root){return root == nullptr ? 0 : std::max(calculateDepth(root->left), calculateDepth(root->right)) + 1;}

5 第k层的节点个数

仿照上面的“节点个数”，这个题就很简单了，只需额外加上一些判断即可

int TreeKlevel(struct TreeNode* root,int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1)return 1;return TreeKlevel(root->left, k - 1) + TreeKlevel(root->right, k - 1);
}

6 相同的树

. - 力扣（LeetCode）

比较两颗树的关键是相同的根的左子树是否等于右子树

但是比较有分很多情况

如果两个节点都为空，那说明相同，返回true

一个为空一个不为空，那说明不相同，返回false

两个均不为空但值不同，说明不相同，返回false

两个均不为空值相同，说明不相同，返回true，需要再往下遍历

其中，递归出口为

如果两个节点都为空，那说明相同，返回true（都遍历到空了，还怎么遍历？）

一个为空一个不为空，那说明不相同，返回false

两个均不为空但值不同，说明不相同，返回false

相同的子函数为

比较两个根的左子树是否相同，再比较两个根的右子树是否相同

由于两棵树相同要同时满足两颗树的左子树相同和两棵树的右子树相同，所以最终结果要并在一起

bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{if (p == NULL && q == NULL)return true;if (p == NULL || q == NULL)return false;if (p->val != q->val)return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

7 单值二叉树

. - 力扣（LeetCode）

这个题我们可以有两种思路

第一种是将树真正的根的值作为参数递归下去，每次比较当前根的值是否等于我们参数中传递的值

这样的话，我们的递归出口就是

当遍历到空就返回true

如果当前根的值不等于我们的参数，就返回false

函数头的设计

由于原题的函数头只有一个TreeNode* ，而我们每次都要传递我们最开始根的值

所以设计一个子函数

    bool _isUnivalTree(TreeNode* root,const int val)

（如果是C++，我们可以写为下面这样，以减少拷贝）

    bool _isUnivalTree(TreeNode* root,const int& val)

相同的子函数

如果当前根的值等于我们的参数，就再遍历左子树+右子树

同理，我们要将结果并在一起

class Solution {
public:bool _isUnivalTree(TreeNode* root,const int val){if(root==nullptr)return true;if(root->val!=val)return false;return _isUnivalTree(root->left,val)&&_isUnivalTree(root->right,val);}bool isUnivalTree(TreeNode* root) {if(root==nullptr)return true;const int val=root->val;return _isUnivalTree(root->left,val)&&_isUnivalTree(root->right,val);}
};

另一种思路是这样的

我们不传递最开始根的值了，每次计算当前根的值，和他的左子树、右子树的值相比较

当然，比较之前要先判空

函数出口为

如果根为空，返回true

如果左子树不为空且值不等于根的值，返回false

如果右子树不为空且值不等于根的值，返回false

相同的子函数

如果当前根和左、右子树的值都相等，就需要比较左子树的根和他的左、右子树是否相等

还有右子树和他的左、右子树是否相等

（感觉也是非常的绕，而且还得判空）

bool isUnivalTree(struct TreeNode* root)
{if (root == NULL)return true;int val = root->val;//比左右孩子时要记得判空if (root->left != NULL && root->left->val != val)return false;if (root->right != NULL && root->right->val != val)return false;return isUnivalTree(root->left) && isUnivalTree(root->right);
}

8 二叉树查找值为x的节点

（默认树中最多只有一个节点等于x）

//找值为x的节点
BTNode* BinaryTreefind(BTNode* root,BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x)return root;BTNode* lret = BinaryTreefind(root->left, x);if(lret!=NULL)return lret;BTNode* rret = BinaryTreefind(root->right, x);if (rret != NULL)return rret;return NULL;
}

这个题就简单了，如果根不是x，左子树先找，如果找到了，就返回；

如果找不到，再去右子树找；找到了，就返回

如果最终都没找到，就返回空

9 对称二叉树

. - 力扣（LeetCode）

这个题就简单了，对称二叉树的关键在于

我的左等于你的右，我的右等于你的左

有了这个认识，这个题就转化成了“相同的树”

当然由于我们比较时需要同时用到左子树、右子树

所以我们还是需要写个子函数

bool _isSymmetric(struct TreeNode* left, struct TreeNode* right)

代码是这样的~

//子函数
bool _isSymmetric(struct TreeNode* left, struct TreeNode* right)
{if (left == NULL && right == NULL)return true;if (left == NULL || right == NULL)return false;if (left->val != right->val)return false;return _isSymmetric(left->left, right->right) && _isSymmetric(left->right, right->left);
}
bool isSymmetric(struct TreeNode* root)
{if (root == NULL)return true;//我的左要等于你的右&&我的右要等于你的左return isSymmetric(root->left, root->right);}

10 层序遍历

. - 力扣（LeetCode）

层序遍历，顾名思义就是将一棵树一层一层遍历

（好消息是这道题终于不是一个递归的题目了）

最简单的就是用队列（queue）

出上一层的同时，引入下一层

他的思路是这样的

1 入根（如果根不为空）

2 当队列不为空的时候，取队头

3 如果队头的左不为空，就入根左

4 如果队头的右不为空，就入根右

5 队列为空时，遍历结束（叶子节点的左右为空，所以队列没有新元素了）

我们给一颗树大概演示一下

1、入根。

队列是这样的

2、根出队列，打印（或其他操作），3的左右均不为空，9，20入队列

队列是这样的

3、队头是9，出队头，但他的左右均为空，所以没有元素入队列

队列是这样的

4、队头是20，出队头，入15，7

队列是这样的

5、出15

6 、出7，结束#

（为了省事，直接上C++了）

 vector<vector<int>> levelOrder(TreeNode* root){queue<TreeNode*> q;vector<vector<int>> vv;int qsize = 0;if (root){//第一层只有一个qsize = 1;q.push(root);}while (!q.empty()){//每次一个vectorvector<int> v;//用qsize控制循环次数for (size_t i = 0; i < qsize; ++i){TreeNode* front = q.front();q.pop();v.push_back(front->val);if (front->left){q.push(front->left);}if (front->right){q.push(front->right);}}vv.push_back(v);qsize = q.size();}return vv;}
};

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

判断是不是完全二叉树_牛客题霸_牛客网 (nowcoder.com)

这个题的关键在于完全二叉树按层序遍历走，非空节点连续

因此我们走一边层序遍历，如果在遇到空节点都还能遇到非空节点，说明不是完全二叉树

bool isCompleteTree(BTNode* root)
{queue<TreeNode*> q;if (root)q.push(root);while (!q.empty()){auto front = q.front();q.pop();if (front == NULL){break;}else//空也插入 之后要用这个判断{q.push(front->left);q.push(front->right);}}while (!q.empty()){auto front = q.front();q.pop();if (front == NULL){return false;}}return true;
}

12 另一棵树的子树

. - 力扣（LeetCode）

有了上面的经验，这道题就简单很多了，当前根节点的值和所给根节点的值相同，

我们就去判断当前根所构成的数和所给的数是否为相同的树即可

 //use相同的树
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{if (p == NULL && q == NULL)return true;if (p == NULL || q == NULL)return false;if (p->val != q->val)return false;return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);//小心别丢了返回值
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot)
{if (root == NULL)return false;//找root的val==subRoot->valif (root->val == subRoot->val){if (isSameTree(root, subRoot)){return true;}}return isSubtree(root->left, subRoot)|| isSubtree(root->right, subRoot);
}