树(Tree)是由$n(n>=0)$个结点组成的一个具有层次关系的非线性有限集合，树中的每个元素被称为树的节点，每个节点有若干个指针指向的后继结点(子结点)。树中节点的子树数目称为节点的度(degree)。树中各结点度的最大值称为树的度，通常称为几次树。度为0的结点称为叶子结点。
二叉树
二叉树每个结点最多只有两个分支，左孩子右兄弟表示法可以将一颗 多叉树转化为二叉树。
- 非完全二叉树：普通二叉树。
- 完全二叉树：除最后一层外，每层的结点数均达到最大值，在最后一层上只缺少右边的结点。
- 满二叉树：除叶子结点外，每个结点都有两个孩子结点，且每一层的结点数都达到最大值。一颗深度为k的二叉树有$2^{k}-1$个结点。
二叉树的性质
性质1：在二叉树的第i层上至多有$2^{i-1} (i>0)$个结点。
性质2：深度为k的二叉树至多有$2^{k}-1 (i>0)$个结点。
性质3：对于任何一颗二叉树，若度为2的结点数目有 n 个，则叶子数必定为 n+1 个。
性质4：具有n个结点的完全二叉树，它的深度必为$\lfloor \log_{2^n} \rfloor +1$
性质5：若完全二叉树上的结点从上至下，从左至右编号，则编号为i(1<=i<=n)的结点，其左孩子编号必为2i，右孩子编号必为2i+1，双亲结点编号必为i/2(i=1除外)。
二叉树的遍历
假设根结点是D，左子树是L，右子树为R，那么：
- 前(根)序遍历 D->L->R
- 中(根)序遍历 L->D->R
- 后(根)序遍历 R->L->D
对于前序遍历第一个节点肯定是根节点，后序遍历最后一个是根节点，中序遍历中根节点两边分别为左子树与右子树。
所以任意已知两种遍历，可以求第三张遍历与树结构。
以上三种遍历都是深度优先搜索算法(depth-first search DFS)。深度优先算发最自然的实现方式是通过递归实现，事实上，大部分树相关的问题都可以优先考虑递归。深度优先算法往往都可以通过使用栈结构将递归转为非递归。这里利用了栈先进后出的特性，其数据的进出顺序与递归顺序一致。
层次遍历(Level traversal)：首先访问第0层，也就是根结点所在的层；当第i层的所有结点访问完之后，再从左至右依次访问第i+1层的各个结点。层次遍历属于广度优先搜索算法(breadth-first search BFS)。广度优先算法一般通过队列数据结构实现。
