C++ 数据结构 (五) 二叉树 (1) 树

应用

树是特殊的图 $ T = (V, E) $, 节点数 $ \vert V \vert = n $, 边数 $ \vert E \vert = e $

指定任一节点 $ r \in V $ 作为根后, $ T $ 即称作有根树 (rooted tree)

若: $ T1, T2, \ldots , Td $ 为有根树

则: $ T = ( ( \bigcup V(i) ) \cup {r}, (\bigcup Ei) \cup \lbrace <r, r(i)> \vert 1 \leq i \leq d \rbrace ) $ 也是

相对于 $ T $, $ T(i) $ 称作以 $ r(i) $ 为根的子树 (subtree rooted at r(i)), 记作 $ T(i) = subtree(r(i)) $

$ r(i) $ 称作 $ r $ 的孩子 (child), $ r(i) $ 之间互称兄弟 (sibling)

$ r $ 为其父亲 (parent), $ r $ 所拥有的孩子数目 $ d = degree(r) $ 为 $ r $ 的 (出) 度 (degree)

可归纳证明: $ e = \sum_{r \in V} \ degree(r) = n - 1 = \Theta (n) $

故在衡量相关复杂度时, 可以 n 作为参照

若指定 $ T(i) $ 作为 $ T $ 的第 $ i $ 棵子树, $ r(i) $ 作为 $ r $ 的第 $ i $ 个孩子, 则 $ T $ 称作有序树 (ordered tree)

$ V $ 中的 $ k+1 $ 个节点, 通过 $ E $ 中的 $ k $ 条边依次相联, 构成一条路径 (通路/path)

$ \pi = \lbrace (V_0, V_1), (V_1, V_2), \cdots , (V_{k-1}, V_k) \rbrace $

路径长度: $ \vert \pi \vert = 边数 = k $

环路 (cycle/loop) : $ V(k) = V(0) $

节点之间均有路径, 称作连通图 (connected)

不含环路, 称作无环图 (acyclic)

所谓的树就是:

故: 任一节点 $ V $ 与根之间存在唯一路径 $ path(v, r) = path(v) $

不致歧义时, 路径、节点和子树可相互指代

$ path(V) \sim V \sim subtree(V) $

$ path \ from \ root \ to \ V \sim V \sim subtree \ rooted \ at \ V $

V 的深度: $ depth(V) = \vert path(V) \vert $

$ path(V) $ 上节点, 均为 $ V $ 的祖先 (ancestor) , $ V $ 是它们的后代 (descendent)

其中, 除自身以外, 是真 (proper) 祖先/后代

半线性: 在任一深度, $ V $ 的 祖先/后代 若存在, 则 必然/未必 唯一

根节点是所有节点的公共祖先, 深度为 0

没有后代的节点称作叶子 (leaf)

所有叶子深度中的最大者称作 (子) 树 (根) 的高度: $ height(V) = height(subtree(V)) $

特别的, 空树的高度取作 $ -1 $

$ depth(V) + height(V) \leq height(T) $

本文由 Oscaner 创作, 采用知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外, 均为本站原创或翻译, 转载前请务必署名