我试图尽可能高效地存储二进制路径(就使用尽可能少的内存而言)。 例如,通向链接二叉树中特定节点的路径(从根开始)——存储该路径的一种简单方法是存储节点(或其值)本身。
但这并不高效,也不优雅。如果我想在不同的二叉树上应用相同的路径,这是行不通的。
所以你可以只保存一个序列,例如一个字符串,例如 "lrllrrr"
哪里l
表示左分支,r
意思是右枝。但是将这些信息存储在字符串中仍然不是很有效。
这可以通过使用 boolean 数组来改进。但我不知道这些在后台的Java中是如何处理的。另外,我想避免固定大小的字符串/数组。
我的下一个想法是直接将路径存储在二进制整数中,例如 0100111
(从左到右阅读)。
然后,您可以使用 <<
添加“向左移动”并使用<<
“向右移动” ,然后是 ++
。但这种方法有三个缺点:
- 在 Java 中,没有无符号整数。我对Java中的按位运算符了解不多,所以我想知道如何处理原语
int
的符号位或long
? - 这种表示形式的条目计数受到组成整数的二进制位数的限制(例如
long
为 63)。这可能可以通过使用BigInteger
来解决. - 至少以一个“左”条目开头的路径无法正确存储,因为在处理整数时,默认情况下会忽略最左边的“0”数字。
那么,Java中有没有什么方法可以存储一系列特定的位,以便我可以轻松地单独读取它们?如果这样的东西确实已经存在,我想了解更多关于它是如何实现的。 如果 Java 中没有这样的东西,并且它太困难或根本不可能,那么您将如何在另一种环境/另一种语言中实现这一点?
提前致谢。
编辑:'0'数字位于最左边
最佳答案
您可以使用单个整数来表示路径。树的大小增加 1、2、4、8 等
另请注意,在谈论“最小”时,请记住内存块大小限制,并且还要注意您的二叉树可能会比您的路径表示大得多。
0
1 2
3 4 5 6
关于java - 存储二进制路径的最有效方法(例如通过二叉树),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59631269/