十二、数据结构基础——树

本章介绍树的遍历（BFS和DFS）、完全二叉树、二叉查找树、并查集等，重点主要是掌握上述知识点的代码实现。

有关树的常见问题有：1）根据序列创建二叉树；2）最近公共祖先问题。

树的结点的定义

树的结点除了存储数据外，还要有一些指向子节点的指针。然而，由于每个子结点数可能不同，需要使用一个vector来存储这些指针，可以用一个类来表示这样一个结点：

树的深度优先遍历

树的先序遍历，代码如下：

树的后序遍历，代码如下：

树的广度优先遍历（层次遍历）

树的层次遍历需要使用一个队列来实现，其代码实现如下：

若希望逐层处理树的不同结点，如在每层的结点输出之后加一个换行符，代码如下：

树的静态写法

树的结点类定义的静态写法如下：

因为数组下标不可能是负数，因此用-1表示结点为空结点。

树的静态写法下的先序、后序、层次遍历代码如下：

二叉树与二叉树的遍历

二叉树结点的定义，代码如下：

二叉树的遍历（先序、中序、后序遍历，层次遍历），代码如下：

完全二叉树

判断一棵树是否是完全二叉树？（核心是层次遍历）若二叉树有N个结点，根节点编号为1，对该二叉树进行层次遍历后，若给定二叉树是完全二叉树，那么遍历得到的结点编号必然会逐一覆盖1~N的N个数字。根据这一点，只需定义一个i从1~N枚举，而后对二叉树进行层次遍历，判断遍历的当前节点是否等于i，即可判断是否完全二叉树。代码如下：

二叉查找树（或称二叉搜索树、二叉排序树）

由于二叉查找树的数据域满足左子树≤根结点＜右子树，因此二叉查找树的中序遍历一定是为升序排列的。

二叉查找树的插入：

二叉查找树的查找：

根据遍历序列创建二叉树的问题

只要给出中序遍历序列和其他任意一种遍历序列，就可以唯一确定一棵二叉树。

①给出中序遍历和先序遍历，创建二叉树：

输出后序遍历序列：

②给出中序遍历和后序遍历，创建二叉树：

输出先序遍历序列：

—————————————————————————————————————————

建立二叉查找树时，只需知道前序遍历序列或者后序遍历序列即可（中序遍历一定是升序）。

③给出先序遍历序列，创建二叉查找树： 

输出二叉查找树的后序遍历：

④给出后序遍历序列，创建二叉查找树： 

需要注意的是，左右子树根节点应该是从右往左找第一个，用rbegin查找到后还需post的大小来得到根结点位置，因此可以将post反转后再操作（就不用传post大小，而且是从左到右顺序查找）。

 输出二叉查找树的先序遍历：

最近公共祖先问题（Lowest Common Ancestor，LCA）

指寻找两个结点所有公共祖先中距离这两个结点最近的祖先节点的问题。

①找到普通二叉树中的p、q结点的LCA，代码如下：

或简写作：

（妙）根据中根遍历和后根遍历建立树并查找两个节点的最近公共祖先：

②找到二叉树查找中的p、q结点的LCA，代码如下：

或简写为：

（妙）根据先序序列建二叉查找树并找到树中两节点的最近公共祖先：

并查集

是一种维护集合的数据结构，它的名字源于合并（union）、查找（find）、集合（set）三个名词。并查集支持两种效率很高的操作：①快速查询两个元素是否在一个集合中；②快速合并两个元素所代表的不同集合。

通常用一个数组ufs来实现并查集。数组下标表示节点的编号，所对应的数组元素的值作为这个节点的父节点。初始情况下，每个节点都是一个集合，即每个结点所在树的根结点都是它本身，有ufs[i]=i。可以通过递归查找结点的父节点最终找到根结点。

1.初始化并查集：

2.查找给定节点所在树的树根结点：

3.合并两个结点所在集合为同一集合（判断两节点的树根是否相同，相同则无需合并，不相同则遵循靠左原则）：

4.路径压缩（即查找时更关注根结点（所在的集合）而非其父节点），只需找到根结点后将ufs[x]改为根结点即可，代码如下：

构建并查集的全部代码如下：