1

我查看了 BST 的一些代码，我可以看到每个节点都是一个结构。这是必要的吗？

4

5 回答 5

7 
int flat_tree[ 1000 ][ 3 ];
    // for each tree node, value is stored in element [id][0]
                        // id of left_child stored in element [id][1]
                        // id of right_child stored in element [id][2]

…</p>

我不会再谈这个了。

一般来说，structs/ classes 用于任何类型的链接数据结构。int同样通常，类型系统的任何功能都可能被击败或忽略，您可以以非常痛苦的方式在一个 s 数组中完成所有操作（堆分配等） 。

于 2010-02-08T05:33:46.253 回答
4

不，它可能是一堂课。它不能是原始的，因为它需要存储一个值并且还指向孩子。

好吧，我应该说你也可以将你的 BST 表示为一个数组，其中 position 节点的左右子节点i分别位于 position2 * i + 1和2 * i + 2。但是你不得不担心调整大小，你需要一个特殊的值来表示 null，并且删除操作变得相当复杂。除了学术练习，我不推荐这种方法。

于 2010-02-08T05:17:47.457 回答
4

它不是强制性的。
但是由于节点包含的数据以及两个链接一起形成了一个逻辑实体，因此它们通常放在一个结构中。这样就可以更轻松地编写将节点作为参数或返回节点的函数。

于 2010-02-08T05:24:21.147 回答
1

不，严格来说不是。在 FORTRAN 时代，人们使用并行数组或二维数组。

Tony Hoare 在 Dahl、Dijkstra 和 Hoare 的“结构化编程”部分讨论了数据结构化和记录类型。

于 2010-02-08T05:40:43.070 回答
0

如果您的有效负载承认一个标记值，您可以比并行数组更简单：您可以使用隐式树（也就是说，根本不用担心链接）。

payload_type a[tree_size];

只是一个只包含有效载荷值的长平面数组，数组中的位置编码为链接结构：

  • a[0]是根
  • a[1]是根->左
  • a[2]是根-> 对
  • a[3]是根->左->左
  • a[4]是根->左->右
  • ...

对于位置 i 的节点，左到 2*i+1，右到 2*i+2

您将其初始化为所有标记值，然后开始添加内容...

于 2010-02-10T20:06:04.867 回答