简介
树 (tree) 是一种广泛使用的抽象数据类型 (ADT) 。
一个简单的无序树如下图：
为何使用树结构？
像链表、栈、数组以及队列的存储序列都是线性数据结构。换句话说，对他们的任何操作的时间复杂度都会随着数据大小增长而增长，在现今的很多计算场景中，这种线性结构是不可接受的。
所以我们需要一种能够更快或更简单的访问数据的数据结构。
相关术语
节点 (Node): 一个包含键值对的实体并且指向他的子节点；边 (Edge)：连接两个节点的链接；根节点 (root)：一个树最顶层的节点；叶子节点 (leaf nodes)：也称为终端节点，没有子树的节点或者度为 0 的节点；节点的高度 (Height of a Node)：从当前节点到最深的叶子节点的边的个数；节点的深度 (Depth of a Node)：从 root 到当前节点的边的个数；节点的度 (Degree of a Node)：当前节点的分支总数；分支节点：也称为非终端节点，度不为零的节点称为非终端节点；层 (level)：从 root 开始，假设 root 为第 1 层，root 的子节点为第 2 层，依此类推，如果某一个节点位于第 L 层，则其子节点位于第 L+1 层。树的深度 (depth)：从 root 找到最大层 (level) 的值叫做树深，也可以叫树高。森林 (Forest)：不相交树的集合
二叉树
二叉树 (binary trees)是树的一种，它的每个节点最多有2个子节点。
满二叉树
若树的每个节点只存在2个或0个子节点，这样的树叫做满二叉树 (full binary tree) 。所以满二叉树的节点要么有 2 个子节点，要么就没有子节点。
完全二叉树
还有一种树被叫做完全二叉树 (complete binary tree) ，它的特点：
- 所有叶子节点
必须靠左； - 叶子节点
允许没有右边的兄弟节点，下面是一个完成二叉树:
满二叉树 VS 完全二叉树
通过下面的图，明确他们之间的区别：
全美二叉树
所有内部节点的度为2。
完美二叉树 (perfect binary tree) 的递归定义：
- 若一个单节点无子节点，则它是一个高度
h = 0的完美二叉树； - 若一个节点的高度
h > 0，则它是一个子树高度都为h - 1的完美二叉树。
下图为三个完美二叉树：
病态或退化树
每个节点只有一个子节点，这样的树可以叫做病态或退化树 (Degenerate or Pathological Tree) 。
平衡二叉树
若任何节点的子树中，左边子树和右边子树的差异 (difference) 不超过 1。这里的差异值为：difference = df = 左边子树的高度 - 右边子树的高度。
下图分别表示了一个平衡二叉树和一个非平衡二叉树：
二叉搜索树
二叉搜索树 (binary search tree) ，简称 BST。也有叫做二叉查找树、有序二叉树或排序二叉树。之所以叫搜索树，因为二叉搜索树能够快速得执行删除、插入、查找等操作。
二叉搜索树的存储结构通常采用二叉链表，是基础性数据结构，用于构建更为抽象的数据结构。在构建时，是有固定排序规则，它是一个有序树。
二叉搜索树的性质：
- 若任意
左子树$\neq \varnothing$，则左子树所有节点值 $<$ root 的值； - 若任意
右子树$\neq \varnothing$，则右子树所有节点值 $>$ root 的值； - 任意节点的左、右子树也分别为二叉查找树。
AVL 树
AVL 树是一种自平衡的二叉搜索树，它的每个节点维护额外的信息，这种信息被叫做平衡因子 (balance factor) 。
在 AVL 树中任何节点的两个子树的高度之差的绝对值最多为 1。
AVL 树得名于它的发明者 G. M. Adelson-Velsky 和 E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
平衡因子
AVL 树中平衡因子是一个节点的左边子树高度和右边子树高度的差异值。
平衡因子 = (左子树的高度 $-$ 右子树的高度) 或 (右子树的高度 $-$ 左子树的高度)
平衡因子的值应该总是-1、0或+1三个值中的其中一个。
旋转子树
在旋转操作中，子树节点位置发生交换，有两种旋转类型：
1.左旋转 (left rotations)
2.右旋转 (right rotations)
3.左右旋转 (left-right and right-left rotations)
- 在左向右旋转中，优先左旋转，然后再右旋转。
- 在左向右旋转中，优先右旋转，然后再左旋转。
树的遍历
通过递归算法来遍历树的节点，可以通过递归函数里决策访问当前节点的时机。
前序遍历
如果要在访问子节点开始之前就访问 (visit) 当前节点，称为前序 (Pre-order) 遍历。它的递归函数流程如下：
visit(currentNode)
traverse(childNodes)
在二叉树中，递归函数表示 NLR (Node-Left-Right) 顺序执行：
visit(currentNode)
traverse(LeftChildNode)
traverse(RightChildNode)
后序遍历
如果要在访问子节点开始之后就访问当前节点，称为后序 (Post-order) 遍历。它的递归函数流程如下：
traverse(childNodes)
visit(currentNode)
在二叉树中，递归函数表示 LRN (Left-Right-Node) 顺序执行：
traverse(LeftChildNode)
traverse(RightChildNode)
visit(currentNode)
中序遍历
中序 (In-order) 遍历是对二叉树而言的，先遍历左子树，而后访问当前节点，再对右子树进行遍历。递归函数表示 LNR (Left-Node-Right) 顺序执行：
traverse(LeftChildNode)
visit(currentNode)
traverse(rightChildNode)
