树

前面已经介绍了顺序表和链表这两种线性数据结构，我们来对比一下在其上执行操作的时间复杂度：

树结构则是将顺序表和链表的优势结合起来，可以理解为链表的链表，也可以认为是二维的链表，由于这个原因，可以认为树型结构既不是我们此前所介绍的线性数据结构，同时它也带有一定的线性特征，为了与之后的非线性数据结构 —— 图相区别，我们不妨称其为半线性数据结构。

树是用来按照层次关系组织一系列数据项的一种方式。

定义：递归嵌套

树是特殊的图 \(T=(V, E)\)，节点数（vertex）\(|V|=n\)，边数（edge）\(|E|=e\)。

指定任一节点 \(r\in V\) 作为根后，\(T\) 即称作有根树（rooted tree）。

通过彼此的嵌套，小型的有根树可以逐步地整合为规模更大的有根树。即若 \(T_1,T_2,...T_d\) 为有根树，则 \(T=((\cup V_i) \cup { r } ,)\) 也是。相对于 \(T\)，\(T_i\) 称作以 \(r_i\) 为根的子树（subtree rooted at \(r_i\)），记作 \(T_i=subtree(r_i)\)。\(r_i\) 称作 \(r\) 的孩子（child），\(r_i\) 之间互称兄弟（sibling）。\(r\) 为其父亲（parent），\(d=degree(r)\) 为 \(r\) 的（出）度（degree），即 \(r\) 的孩子的数目。

可归纳证明：\(e=\sum_{r\in V} degree(r)=n-1=\Theta(n)\)，即任何一棵树中，所含的边数（\(e\)）应该恰好等于其中所有顶点的度数之和，同时也恰好等于顶点总数（\(n\)）减 1，故在衡量相关复杂度时，可以 \(n\) 作为参照。

若指定 \(T_i\) 作为 \(T\) 的第 \(i\) 棵子树，\(r_i\) 作为 \(r\) 的第 \(i\) 个孩子，则 \(T\) 称作有序树（ordered tree）。

定义：连通性+无环性

\(V\) 中的 \(k+1\) 个节点，通过 \(E\) 中 \(k\) 条边依次相联，构成一条路径（path），亦称通路。表示为： \[\pi=\{(v_0, v_1), (v_1, v_2), ..., (v_{k-1}, v_k)\}\]

其中路径长度：\(|\pi|=边数=k\)。在早期文献中，或以节点数为长度。

所谓环路（cycle/loop），即 \(v_k=v_0\)

节点之间均有路径，称作连通图（connected）。不含环路，称作无环图（acyclic）。

所谓的树，其实就是在无环与连通之间达到一个平衡的一种特定的图，因为无环，所以它的边数不会太大，反之，因为连通，所以它的边数又不能太少（无环连通图）；在保证连通的前提下，它的边数能够达到最少（极小连通图）；而在杜绝环路的前提下，它又能够使用尽可能多的边（极大无环图）。

从以上可得，任一节点 \(v\) 与根之间存在唯一路径，即 \(path(v, r)=path(v)\)，因此每一个节点拥有了一个唯一的指标，也就是这条路径的长度。

不致歧义时，路径、节点和子树可相互指代，即 \(path(v)\sim v\sim subtree(v)\)，因此，\(v\) 的深度：\(depth(v)=|path(v)|\)。

此外，\(path(v)\) 上节点，均为 \(v\) 的祖先（ancestor），\(v\) 是它们的后代（descendent），其中，除自身以外，是真（proper）祖先/后代。

所谓的半线性，即在任一深度，\(v\) 的祖先若存在，则必然唯一；\(v\) 的后代若存在，则未必唯一。

根节点是所有节点的公共祖先，深度为 0，没有后代的节点称作叶子（leaf），所有叶子深度中的最大者称作（子）树（根）的高度，即 \(height(v)=height(subtree(v))\)。

特别地，空树的高度取做 -1。

任何一个节点的高度与深度之和绝对不会超过全树的高度，即 \(depth(v)+height(v)\leq height(T)\)。

表示

为兼顾空间性能和时间性能，通常采用长子-兄弟表示法表示一棵树。即每个节点均设两个引用：纵（firstChild()）和横（nextSibling()）。