实现1:
struct treenode{
int data;
struct treenode children[2];
}
实现2:
struct treenode{
int data;
struct treenode *children;
}
这是我的想法:
实现 2 在空间复杂度方面会更好,因为
- 未定义的子项不需要在 imp 中进行 malloc。 2、同时(我推测) imp.1 中的数组在声明时自动为两个树节点分配空间?
但是,对于这两种实现,每个节点最终都只携带一个 int 和一个指针,因此空间复杂度不会相差那么大,对吗?我使用实现 1 来避免使用双指针和混淆的可能性(哈哈...),当我尝试构建具有大量数据的树时,我的程序最终被“杀死”。我的很多同学都没有这个问题,而且我偏离了教授暗示我们应该构建树的方式(使用实现 2)。
我是否很可能因为使用实现 1 而遇到此问题?如果两个节点最终携带相同的东西,为什么问题会更大呢?是因为大数据导致大量叶节点在一种情况 (1) 中被分配,但在另一种情况 (2) 中却没有分配?或者我对每种情况下空间复杂度如何不同的解释完全错误?
最佳答案
您是否尝试过编译实现 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 是什么。
关于比较这些二叉树节点实现的空间复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59148433/