5.1 树

有根树
树是特殊的图T = (V, E)，节点数|V| = n，边数|E| = e
指定任一节点r ∈ V作为根后，T即称作有根树(rooted tree)
若T₁，T₂，...，T_d为有根树，则T = ((∪V_i)∪{r}, (∪E_i)∪{<r, r_i> | 1 ≤ i ≤ d})是有根树
相对于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（度）
e = Σ_r∈Vdegree(r) = n - 1 = Θ(n)，e为边数，n为节点数
在衡量相关复杂度时，以n作为参照
若指定T_i作为T的第i个子树，r_i作为r的第i个child，则T称作有序树(ordered tree)

路径
V中的k+1个节点，通过E中的k条边依次相联，构成一条路径(path)
π = {(v₀, v₁), (v₁, v₂), ..., (v_k-1, v_k)}
路径长度 |π| = 边数 = k
环路(cycle / loop) v_k = v₀
节点间均有路径，称作连通图(connected)
不含环路，称作无环图(acyclic)
树是无环连通图、极小连通图、极大无环图
任一节点v与根之间存在唯一路径path(v, r) = path(v)
不致歧义时，路径、节点、子树可相互指代，path(v) ~ v ~ subtree(v)
v的深度depth(v) = |path(v)|
path(v)上的节点，均为v的ancestor，v是其后代descendent，其中除自身外，是真proper ancestor / descendent
半线性：在任一深度v的ancestor / descendent若存在，则必然/未必唯一
根节点是所有节点的公共ancestor，深度为0
无后代的节点称作leaf，所有leaf深度中最大者，称作树的高度height(v) = height(subtree(v))
空树的高度取作-1
depth(v) + height(v) ≤ height(T)

接口
root() 根节点
parent() 父节点
firstChild() 第1个子节点
nextSibling() 兄弟节点
insert(i, e) 将e作为第i个子节点插入
remove(i) 删除第i个子节点（及其后代）
traverse() 遍历

表示方法：每个节点均设两个引用，纵向firstChild()，横向nextSibling()
除根外，任一节点有且仅有一个父节点