比较 space 这些二叉树节点实现的复杂性？

Question

实施 1：

struct treenode{
    int data;
    struct treenode children[2];
}

实施 2：

struct treenode{
    int data;
    struct treenode *children;
}

这是我的想法：

实施 2 在 space 复杂性方面会更好，因为

未定义 children imp 中不需要 malloc。 2，而（我假设） imp.1 中的数组在声明时自动为两个树节点 malloc space?

然而，对于这两种实现，每个节点最终只携带一个 int 和一个指针，所以 space 复杂度不会有太大差异，对吧？我使用实现 1 来避免使用双指针和混淆的可能性（哈哈...），当我尝试构建具有大量数据的树时，我的程序最终得到 "Killed"。我的很多同学都没有这个问题，我也偏离了教授暗示我们应该构建树的方式（使用实现 2）。

我遇到这个问题的可能性很大是因为我使用了实施 1？如果两个节点最终都携带相同的东西，为什么问题要多得多？是不是因为大数据导致大量叶节点在一种情况 (1) 中被分配，但在另一种情况 (2) 中却没有分配？或者我对 space 复杂性在每种情况下有何不同的解释完全错误？

Answer 1

你试过编译实现1吗？

让我们考虑一下。实施 1 中 struct treenode 的大小是多少？

假设 data 是 4 个字节。 children 的大小是多少？它是 struct treenode 的 2 元素数组，因此它的大小必须是 struct treenode 的 2 倍。那么struct treenode的大小是多少？

假设 data 是 4 个字节...等一下。你可以在这里看到问题。

当我写这个答案时，实现 1 被定义为：

struct treenode{
    int data;
    struct treenode children[2];
}

我怀疑这不是 OP 编写的实际程序中的内容，因为它不会编译。也许他的意思是：

struct treenode{
    int data;
    struct treenode *children[2];
}

但在那种情况下，我想知道实现 2 是什么。

比较 space 这些二叉树节点实现的复杂性？

Compare space complexity of these binary tree node implementations?

c

malloc

binary-tree