0

我已经在 C 中实现了一个基于一系列链表的数据结构，它看起来类似于树 - 但不足以被称为树，因为理论上它允许存在循环。这是节点的基本轮廓：

  • 有一个单一的、可识别的根，它没有父节点或兄弟；
  • 每个节点都包含一个指向它的“父亲”、最近的“兄弟”和他的第一个“孩子”的指针；
  • 有没有孩子和兄弟的“外部”节点。

如何命名这样的数据结构？它不可能是一棵树，因为即使指针被清楚地标记和使用不同，像父亲->孩子->兄弟->父亲这样的循环也很可能存在。我的问题是：诸如“父亲”、“孩子”和“兄弟”之类的术语可以在图形的上下文中使用，还是只为树保留？经过相当多的研究，我仍然无法澄清这个问题。

提前致谢！

4

1 回答 1

0

我想说你仍然可以称它为树，因为基础是树数据结构。我的主张有优先权：“Patricia Tries”被称为树，即使它们的叶节点可能指向树（创建循环）。我相信还有其他例子。

听起来您拥有的其他链接本质上只是为了方便，并且可以隐式确定（而不是显式存储）。通过显式存储它们，您可以对树操作（插入、删除等）施加额外的不变量，但不会影响底层组织，即树。

正是因为您分别命名和处理这些附加链接，所以可以将它们视为树顶部的“覆盖”。

最后，如果它适合你，你怎么称呼它或者它属于什么类别并不重要。阅读像 Sedgewick 的“C 中的算法”这样的书，您会意识到那里有大量的数据结构，而自己发明并没有错！

还有一点：树是图的一种特殊情况，因此将其称为图（或在其上使用图算法）也没有错。

于 2013-07-30T17:35:59.247 回答