树的概念

树(tree)是一种能够分层存储数据的重要数据结构，树中的每个元素被称为树的节点，每个节点有若干个指针指向子节点。从节点的角度来看，树是由唯一的起始节点引出的节点集合。这个起始结点称为根(root)。树中节点的子树数目称为节点的度(degree)。在面试中，关于树的面试问题非常常见，尤其是关于二叉树(binary tree)，二叉搜索树(Binary Search Tree, BST)的问题。

所谓的二叉树，是指对于树中的每个节点而言，至多有左右两个子节点，即任意节点的度小于等于2。而广义的树则没有如上限制。二叉树是最常见的树形结构。二分查找树是二叉树的一种特例，对于二分查找树的任意节点，该节点存储的数值一定比左子树的所有节点的值大比右子树的所有节点的值小“(与之完全对称的情况也是有效的：即该节点存储的数值一定比左子树的所有节点的值小比右子树的所有节点的值大)。

基于这个特性，二分查找树通常被用于维护有序数据。二分查找树查找、删除、插入的效率都会于一般的线性数据结构。事实上，对于二分查找树的操作相当于执行二分搜索，其执行效率与树的高度(depth)有关，检索任意数据的比较次数不会多于树的高度。这里需要引入高度的概念：对一棵树而言，从根节点到某个节点的路径长度称为该节点的层数(level)，根节点为第0层，非根节点的层数是其父节点的层数加1。树的高度定义为该树中层数最大的叶节点的层数加1，即相当于于从根节点到叶节点的最长路径加1。由此，对于n个数据，二分查找树应该以“尽可能小的高度存储所有数据。由于二叉树第L层至多可以存储 2^L 个节点，故树的高度应在logn量级，因此，二分查找树的搜索效率为O(logn)。

直观上看，尽可能地把二分查找树的每一层“塞满”数据可以使得搜索效率最高，但考虑到每次插入删除都需要维护二分查找树的性质，要实现这点并不容易。特别地，当二分查找树退化为一个由小到大排列的单链表(每个节点只有右孩子)，其搜索效率变为O(n)。为了解决这样的问题，人们引入平衡二叉树的概念。所谓平衡二叉树，是指一棵树的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。通过恰当的构造与调整，平衡二叉树能够保证每次插入删除之后都保持平衡性。平衡二叉树的具体实现算法包括AVL算法和红黑算法等。由于平衡二叉树的实现比较复杂，故一般面试官只会问些概念性的问题。

满二叉树(full binary tree)：如果一棵二叉树的任何结点，或者是叶节点，或者左右子树都存在，则这棵二叉树称作满二叉树。

完全二叉树(complete binary tree)：如果一棵二叉树最多只有最下面的两层节点度数可以小于2，并且最下面一层的节点都集中在该层最左边的连续位置上，则此二叉树称作完全二叉树。

Free tree

指的是相互连接的无环无向图

假设 G = (V, E) 是一个无向图，那么下面的语句是等价的：

G 是一个 free tree
G 中的任意两个节点间都有唯一的一条路径
G 是连通的的，但是如果去掉任何一条边，G 就不连通了
G 是连通的，并且 $|E|=|V|-1$
G 是无环的，并且 $|E|=|V|-1$
G 是无环的，但是加入任何一条新的边，就会变成有环的

Forest 森林

同样是无环无向图，但不是所有的节点都是连通的

下图中包含一个环，所以不能算是森林：

Rooted Tree

有根的树也是一棵 free tree，但是其中一个节点和其他不同，称为根。有根树中有一些概念需要理解清楚，这里只列举出来不再赘述：ancestor, descendant, proper ancestor, proper descendant, parent, child, siblings, external node(leaf), internal node。

一个节点的孩子数量称之为节点的度(degree)，从根到某节点的要经过的边的数量就是该节点的深度，最大的深度称为树的高度。

根树有几个特例，也非常常用，需要理解清楚，这里列举如下：

Binary tree
Full binary tree: each node is either a leaf or has degree exactly 2
Complete k-ary tree: a k-ary tree in which all leaves have the same depth and all internal nodes have degree k
Binary search tree: 一个节点的左右子节点和节点本身满足一定的大小关系

树的遍历

这一部分也是非常重要的内容，基本来说各类考点都在这里，不但需要对概念的清晰理解，还需要利用递归来解决问题（虽然不用递归也可以），主要有下面这四类：

前序遍历
中序遍历
后序遍历
层次遍历

具体的概念可以在 wiki 上查看，注意一下层次遍历可能需要一些特殊处理即可。

二叉树的常见操作包括树的遍历，即以一种特定的规律访问树中的所有节点。常见的遍历方式包括：

前序遍历(Pre-order traversal)：访问根结点；按前序遍历左子树；按前序遍历右子树。
中序遍历(In-order traversal)：按中序遍历左子树；访问根结点；按中序遍历右子树。特别地，对于二分查找树而言，中序遍历可以获得一个由小到大或者由大到小的有序序列。
后续遍历(Post-order traversal)：按后序遍历左子树；按后序遍历右子树；访问根结点。

以上三种遍历方式都是深度优先搜索算法(depth-first search)。深度优先算法最自然的实现方式是通过递归实现，事实上，大部分树相关的面试问题都可以优先考虑递归。此外，另一个值得注意的要点是：深度优先的算法往往都可以通过使用栈数据结构将递归化为非递归实现。这里利用了栈先进后出的特性，其数据的进出顺序与递归顺序一致(请见 Stack and Queue) 。

层次遍历(Level traversal)：首先访问第0层，也就是根结点所在的层；当第i层的所有结点访问完之后，再从左至右依次访问第i+1层的各个结点。层次遍历属于广度优先搜索算法(breadth-first search)。广度优先算法往往通过队列数据结构实现。