树是一种有限节点组成一个具有层次关系的集合，把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，叶朝下。每个节点有零个或多个子节点，没有父节点的节点称为根节点，除了根节点以外，每个节点都有且仅有一个父节点，并且树里面没有环路。空集合也是树，称为空树，空树中没有节点。
树的常见术语
父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
子节点：一个节点含有的子树的根节点称为该节点的子节点。
叶子节点：没有子节点的节点称为叶子节点。
兄弟节点：具有相同父节点的节点互称为兄弟节点。
节点的度：一个节点含有的子节点的个数称为该节点的度。
树的度：一棵树中，最大节点的度称为树的度。
节点的层次：根节点的层次为 1 ，其他节点的层次等于它父节点的层次数加 1 。
节点的深度：根节点的深度为 0 ，其他节点的深度等于它父节点的深度数加 1 。
树的深度：距离根节点最远的节点深度为树的深度。
节点的高度：所有叶子节点的高度为 0 ，其他节点的高度等于它所有子节点中的最大高度加 1。
树的高度：从根节点到到一个叶子节点的最长路径长度。
堂兄弟节点：父节点在同一层的节点互为堂兄弟节点。
节点的祖先：从根节点到该节点这条分支上的所有节点。
子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
森林：指若干棵互不相交的树的集合。
前驱节点：对一棵二叉树进行中序遍历，遍历后的结果中，当前节点的前一个节点为该节点的前驱节点；
后继节点：对一棵二叉树进行中序遍历，遍历后的结果中，当前节点的后一个节点为该节点的后继节点；
二叉树：每个节点最多含有两个子树的树称为二叉树。
完全二叉树：对于一棵二叉树除了最下面一层外，其它各层的节点数目均已达最大值，且最后一层的所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树。
满二叉树：所有叶节点都在同一层的完全二叉树称为满二叉树，也可以理解除了叶子节点以外的所有节点均含有两个子节点的树称为满二叉树。如图所示，中间的二叉树，虽然上面各层的节点数目都已达到最大值，但最后一层的节点不是从左往右紧密排列的，所以他不是完全二叉树。
完全二叉树的特性：
- 第
i层上的节点数目最多为2^(i-1)。 - 度为
1的节点仅有1个或0个（叶子节点尽可能往左排）。 - 叶子节点的个数 =
(n+1)/2（n 是二叉树所有节点的数量）。
如果让完全二叉树的根节点编号为 0 ，把其他节点从上到下从左到右一个个编上号，会有下面的对应关系。
父节点的下标 = (子节点下标-1) >> 1;（根节点不考虑）
左子节点下标 = 父节点下标*2 + 1;
右子节点下标 = 父节点下标*2 + 2;
满二叉树的特性：
- 共有
(2^k)-1个节点（k是总的层数）。 - 节点个数一定是奇数。
- 第
i层有2^(i-1)个节点。 - 有
(n+1)/2个叶子节点（n是总的节点数量）。 - 叶子节点的度都为
0，非叶子节点的度都是2，没有度为1的节点 。
| 数组，滚动数组，差分数组，树状数组 | |
| 链单向表，双向链表，循环链表，跳表，异或链表 | |
| 队列，循环队列，双端队列 | |
| 栈 | |
| 散列表 | |
| 二叉树，二叉搜索树，AVL树，红黑树，字典树，哈夫曼树，线段树，笛卡尔树 | |
| 堆 | |
| 图的介绍，图的遍历，Dijkstra算法，Bellman-Ford算法，SPFA算法，Floyd算法，Prim算法，Kruskal算法，Boruvka算法，拓扑排序 |
