二叉搜索树中是否需要结构体

Question

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

Answer 1

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]

...

我不会去任何进一步与此有关。

一般而言，structs / classes被用于任何类型的链接的数据结构。还通常，类型系统的任何特征可以被击败或忽略，可以在很痛苦的方式做在ints的一个阵列的一切（堆分配等）。

Answer 2

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

好了，我应该说，你也可以代表你的BST作为一个数组，其中在位置i节点的左，右孩子都在位置2 * i + 1和2 * i + 2，分别。但是，那么你就不必担心调整，你需要一个特殊的值来表示空和删除操作变得相当复杂。我不推荐这种方法，因为不是一个学术活动以外的任何其他。

Answer 3

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

Answer 4

没有，不是严格意义。在FORTRAN日子里，人们使用的平行阵列，或者二维阵列。

“结构化编程”，由达尔，Dijkstra算法和霍尔的东尼·霍尔的部分，谈到数据结构和记录类型。

Answer 5

如果您的有效负载允许一个哨兵值，您可以做比并行数组更简单的事情：您可以使用隐式树（即根本不用担心链接）。

payload_type a[tree_size];

只是一个仅包含有效负载值的长平面数组，其位置在数组编码中用于链接结构：

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

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

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