树
树是一种层次结构。
树的特性：
- 树结构中，每个节点的深度都是一个非负整数。
- 深度为1的节点有且仅有一个，称作树的根（Root）。
- 对于深度为K(k>1)的节点，都有且仅有一个深度为K-1的节点与之对应，称为此节点的父节点。
- 若节点B的父节点是A，则B称为A节点的孩子。具有共同父亲的节点之间称为兄弟节点。
- 树总是从父亲节点指向孩子节点，形成一条树边。
- 树中节点数目总=树边总数+1。
- 所有节点中具有最大深度的节点的深度称为树的深度或高度。树的深度，从根节点（深度为1）向下累加，某节点的深度就是根节点累加到此节点（包含）的数值；树的高度，从叶子节点向上累加，父节点的高度就是其深度最深的叶子节点（高度为1）向上累加到它的数值。
- 任一节点的孩子总数，称为此节点的度（Degree）。
- 树的节点总数=树的节点度数之和*2+1。
- 拥有孩子的节点称为内部节点（internal node），没有孩子的节点称为外部节点（external node）或叶子节点（leaf）。
- 由树中 k+1 节点通过树边首尾衔接而构成的序列{ (v 0 , v 1 ), (v 1 , v 2 ), …, (v k-1 , v k ) | k ≥ 0}，称作树中长度为 k 的一条路径（Path）。
- 树中任何2个节点间都存在唯一的一条路径。
- 从树根通往任一节点的路径长度，恰好等于该节点的深度-1，即深度=路径长度+1。
- 树T中每一节点V的所有后代也构成一棵树，称作T的以V为根的子树（Subtree）。
- 在树T中，若在每个节点的所有孩子之间都可以定义某一线性次序，则称T为一棵有序树（Ordered tree）。
- 每个内部节点均为m度的有序树，称作m叉树。
二叉树
- 每个节点都不超过2度的有序树，称作二叉树（binary tree）。
- 不含1度节点的二叉树，称作真二叉树（proper binary tree），否则称为非真二叉树（improper binary tree）。
- 二叉树中。深度为K的节点不超过2的k-1次方个。
- 高度为k的二叉树做多包含2的k次方-1个节点。
- 由n个节点构成的二叉树，高度至少为log2n（2为底数n的对数）。
- 二叉树中，叶子节点总是比2度节点多一个。
满二叉树
若二叉树T中所有叶子节点的深度完全相同，称为满二叉树（full binary tree）。
包含root节点，高度和深度相同都等于层数，设k为层数：
- 第k层的叶子（孩子）数是2的k次方：2^k
- 第k层的节点数是2的k-1次方：2^(k-1)
- 总结点数是2的k次方减1：2^k - 1
完全二叉树
一棵满二叉树中，从最右侧起将相邻的若干叶子节点摘除，得到的二叉树称为完全二叉树（complete binary tree）。
拥有n个节点的完全二叉树，其叶子节点数是n除以2并向上取整（有小数直接进1），或n+1除以2并向下取整（忽略小数）。
n个节点构成的完全二叉树，高度h=log[2]n(2为底数的对数)。
由n个节点构成的二叉树中，完全二叉树的高度最低。
完全二叉树的数组存储结构
将节点v的位置记为i(v)，则根节点编号i(root) = 0，i(lchild(root)) = 1，i(rchild(root)) = 2，i(lchild(lchild(root)) = 3 ，…。
则：
- 若节点v有左孩子，则i(lchild(v))=2*i(v)+1;
- 若节点v有右孩子，则i(rchild(v))=2*i(v)+2;
- 若节点v有父亲，则i(parent(v))=⎣(i(v) - 1)/2⎦ = ⎡(i(v)/2⎤ - 1(取下限和取上限)。
二分查找树
二叉查找树(Binary Search Tree)，又被称为二叉搜索树。设x为二叉查找树中的一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。
AVL树
在二分查找树T中，若所有节点的平衡因子的绝对值均不超过1，则称T为一棵AVL树。完全二叉树必然是AVL树。由n个节点构成的AVL树的高度为log2。
高度为h的AVL树，至少包含Fib(h+2)-1个节点。