首页 文章

Java Serialize包含许多空节点的N树

提问于
浏览 次
0

我有一个N-ary树，其中每个节点包含一些数据及其子节点：

Node {
  // data
  Node[] children = new Node[30];
}

如您所见，无论当前的后代数量如何，子数组的大小都固定为30 . 该数组可以包含以下内容：

null, null, someNode, null, anotherNode, ...

像这样的树总是不完整的;因此，我无法将其序列化为 c 子位于 N * i + 1 + c （父节点的索引为 i ）的数组 .

我可以使用 / 符号通过前序遍历来序列化树，以表示 null child，但此方法需要 n*30*sizeOfData 个字节 . 即使我代表没有孩子，例如 # ，也需要 n*30*sizeOfData - numberOfLeafs*29 ，这太多了 .

如果您知道更好的方法来序列化这样的树，请写信给我;）

提前致谢 .

java algorithm serialization tree

3 回答

  • 0

    如果现有孩子的一部分很小，你最好明确地写下这样的孩子的索引

    2: somenode
4: othernode

    在读取期间，只用空值填充未使用的条目

    回复于
  • 1

    考虑到你使用Java，因为你已经将它作为标记提到，你可以使用Hashmap而不是Node []，你最终会得到这样的结果：

    Node {
     // data
     HashMap<Integer, Node> children; //Integer is index of child and Node is actual child, TODO: init it and write some function to control add/swap/delete children
   }

    现在为什么我建议你这样做，我会在这里回答：

    • 您将摆脱以前型号中浪费的空间 .

    • 你将拥有像数组一样的索引，你可以循环遍历这个 Map ，并使用索引和子代码以你喜欢的顺序遍历它 .

    我希望这可以帮助你 .

    回复于
  • 1

    需要更多的重复，或者我会将其添加为评论而不是回答 .

    序列化接口还允许添加readObject / writeObject方法，因此通过MBo实现建议有点容易：

    回复于

相关问题