接口
| 节点 | 功能 |
|---|---|
| root() | 根节点 |
| parent() | 父节点 |
| firstChild() | 长子 |
| nextSibling() | 兄弟 |
| insert(i, e) | 将 e 作为第 i 个孩子插入 |
| remove(i) | 删除第 i 个孩子 (及其后代) |
| traverse() | 遍历 |
父节点表示法
观察: 除根外，任一节点有且仅有一个父节点
构思: 将节点组织为序列，各节点分别记录 (data为本身信息，parent为父节点的秩或位置)
空间性能: $ O(n) $
时间性能:
- parent(): $ O(1) $
- root(): $ O(n) $ or $ O(1) $
- firstChild(): $ O(n) $
- nextSibling(): $ O(n) $
孩子节点表示法
父亲孩子表示法
长子兄弟表示法
每个节点均设两个引用
- 纵: firstChild()
- 横: nextSibling()
本文由
Oscaner
创作, 采用
知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外, 均为本站原创或翻译, 转载前请务必署名
