C++ 数据结构(五)二叉树(1)树
     发布在:C/C++      浏览:35      评论:0 条评论

上一篇:《C++ 数据结构(四)栈与队列(3)队列接口与实现》

应用

1、层次关系的表示

  • 表达式:RPN

  • 文件系统

  • URL ...

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

有根树

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

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

若:T1, T2, ..., Td 为有根树

则:T = ( ( ∪V(i) ) ∪ {r}, (∪Ei) ∪ { <r, r(i)> | 1 ≤ i ≤ d } ) 也是

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

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

有序树

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 = { (V_0, V_1), (V_1, V_2), \cdots , (V_{k-1}, V_k) } $$

路径长度:|π| = 边数 = k

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

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

连通 + 无环

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

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

所谓的树就是:1、无环连通图;2、极小连通图;3、极大无环图

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

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

深度 + 层次

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

path(V) ~ V ~ subtree(V)

path from root to V ~ V ~ subtree rooted at V

V 的深度depth(V) = |path(V)|

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

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

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

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

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

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

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

depth(V) + height(V) ≤ height(T)

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

下一篇:《C++ 数据结构(五)二叉树(2)树的表示》

Responses