C++ 数据结构(五)二叉树(2)树的表示
     发布在:C/C++      浏览:34      评论:0 条评论

上一篇:《C++ 数据结构(五)二叉树(1)树》

接口

节点 功能
root() 根节点
parent() 父节点
firstChild() 长子
nextSibling() 兄弟
insert(i, e) 将 e 作为第 i 个孩子插入
remove(i) 删除第 i 个孩子(及其后代)
traverse() 遍历

父节点表示法

观察:除根外,任一节点有且仅有一个父节点

构思:将节点组织为序列,各节点分别记录(data为本身信息,parent为父节点的秩或位置)

空间性能:O(n)

时间性能:

  • parent():O(1)

  • root():O(n)或O(1)

  • firstChild():O(n)

  • nextSibling():O(n)

C++ 数据结构(五)二叉树(2)树的表示

孩子节点表示法

C++ 数据结构(五)二叉树(2)树的表示

父亲孩子表示法

C++ 数据结构(五)二叉树(2)树的表示

长子兄弟表示法

每个节点均设两个引用

  • 纵:firstChild()

  • 横:nextSibling()

C++ 数据结构(五)二叉树(2)树的表示

下一篇:《C++ 数据结构(五)二叉树(3)二叉树概述》

Responses