树是一种数据结构，它是由n(n>= 0)个有限节点组成的一个具有层次关系的集合。把它叫做树是因为它看起来像是一颗倒挂的树，也就是说它是根朝上，叶朝下的。它具有以下的特点：
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点之外，每个子节点可以分为多个不相交的子树。
树是包含n(n>=0)个节点，当n=0时，称为空树，非空树(n-1)条边的有穷集，在非空树中：
- 每个元素称为节点。
- 有一个特点的节点称为根节点。
- 除根节点之外的其余元素被分为m个互不相交的集合，其中每一个集合本身也是一棵树，被称作子树。
空集合也是树，称为空树。空树中没有节点。
孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点。
节点的度：一个节点拥有的直属的子节点的个数称为该节点的度。
叶节点或终端节点：度为0的节点称为叶节点。
树的度：一棵树中，最大的节点的度称为树的度。
节点的层次：从根节点开始，根节点为第1层，根的子节点为第2层，以此类推。
树的高度或深度：树中的节点的最大层次数。
无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树。无序树中，各个结点的左子树和右子树的位置可以交换。
有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树。有序树中各个结点的左子树和右子树的位置不能交换。
二叉树：每个节点最多包含两个子树的树称为二叉树。
满二叉树：二叉树中所有非叶子节点的度都是2（节点包含两个子树），且叶子节点都在同一层上。
完全二叉树：除最后一层外，所有层都是满节点，且最后一层缺右边连续节点的二叉树称为完全二叉树。即一个二叉树与满二叉树前m个节点的结构相同。
二叉搜索树-BST：二叉搜索树是有序的二叉树。指一颗空树或者具有下列特征的二叉树：
- 若任意节点的左子树不为空，则左子树上所有节点的值均小于它根节点的值。
- 若任意节点的右子树不为空，则右子树上所有节点的值均大于它根节点的值。
- 任意节点的左，右子树也分别为二叉搜索树。
- 没有键值相等的节点。
平衡二叉树-AVL：AVL可以定义为平衡二叉搜索树，其中每个节点与平衡因子有关，该平衡因子通过从其左子树的子树中减去其右子树的高度来计算。含有相同节点的二叉搜索树有不同的形态，而二叉搜索树的平均查找长度与树的深度有关，查找平均长度最小的一种树就是平衡二叉树，具有一下性质：
- 要么是空树，要么根节点左右子树的深度之差绝对值不超过1。
- 其左右子树也是平衡二叉树。
- 二叉树节点的平衡因子定义为该节点的左子树深度减去右子树的深度。而平衡二叉树所有节点的平衡因子只能是-1,0,1。
如果每个节点的平衡因子在-1到1之间，则称树是平衡的，否则树就是不平衡的，并且需要平衡。
平衡系数 = 高度（左）- 高度（右）
- 如果任何节点的平衡因子为1，则意味着左子树比右子树高一级。
- 如果任何节点的平衡因子为0，则意味着左子树和右子树高度一致。
- 如果任何节点的平衡因子为-1，则意味着左子树比右子树低一级。
定义一棵树的根节点层次为1，其他节点的层次是其父节点层次加1。一棵树中所有节点的层次的最大值称为树的深度。