二叉树（Binary Tree）：

  1. 要么二叉树没有根节点，是一棵空树。
  2. 要么二叉树由根节点、左子树、右子树组成，且左子树和右子树都是二叉树。

满二叉树：

每一层的节点数都达到了当层能达到的最大结点数。

齐全二叉树：

定义：除了最上面一层外，其余层的结点个数都达到了当层能达到的最大结点数，且最上面一层只从左至右间断存在若干结点，而这些间断结点左边的结点全副不存在。

小技巧：

1. 判断某个结点是否为叶结点的标记为：该结点（记下标为root）的左子结点的编号root*2大于结点总个数n。

2. 判断某个结点是否为空结点的标记为：该结点下标root大于结点总个数n。

二叉查找树（Binary Search Tree）：

  1. 要么二叉查找树是一棵空树。
  2. 要么二叉查找树由根节点、左子树、右子树组成，其中左子树和右子树都是二叉查找树，且左子树上所有结点的数据域均小于或等于根结点的数据域，右子树上所有结点的数据域均大于根节点的数据域。

均衡二叉树（AVL树）：

AVL树依然是一棵二叉查找树（Binary Search Tree），对于AVL树的任意结点来说，其左子树和右子树的高度之差的绝对值不超过1。

其中左子树和右子树的高度之差称为该结点的均衡因子。

并查集：

并查集是一种保护汇合的数据结构，并查集反对上面两个操作：

  1. 合并：合并两个汇合。
  2. 查找：判断两个元素是否在一个汇合。

堆：

堆是一棵齐全二叉树，用priority_queue实现即可，priority_queue默认是大顶堆，如果想用小顶堆，就采纳上面的代码：

priority_queue<int,vector<int>,greater<int>> q 数字越小优先级越大 。

度（对树而言）：

把结点的子树棵数称为结点的度（degree）,而树中结点的最大的度称为树的度（也称为树的宽度）。

度（对图而言）：

顶点的度是指和该顶点相连的边的条数，特地是对于有向图来说，顶点的出边条数称为该顶点的出度，顶点的入边条数称为该顶点的入度。

最小生成树：

最小生成树（Minimum Spanning Tree,MST）是在一个给定的无向图 G(V,E)中求一棵树T，使得这棵树领有图G中的所有顶点，且所有边都是来自图G中的边，并且满足整棵树的边权之和最小。

最小生成树有3个性质须要把握：

  1. 最小生成树是树，因而其边数等于顶点数减1，且树内肯定不会有环。
  2. 对给定的图G(V,E)，其最小生成树能够不惟一，但其边权之和肯定是惟一的。
  3. 因为最小生成树是在无向图上生成的，因而其根节点能够是这棵树上的任意一个结点。如果题目中波及最小生成树自身的输入，为了让最小生成树惟一，个别都会间接给出根节点，读者只须要以给出的结点作为根节点来求解最小生成树即可。

参考书目：《算法笔记》