java - 存储二进制路径的最有效方法(例如通过二叉树)

Question

我试图尽可能高效地存储二进制路径(就使用尽可能少的内存而言)。例如，通向链接二叉树中特定节点的路径(从根开始)——存储该路径的一种简单方法是存储节点(或其值)本身。

但这并不高效，也不优雅。如果我想在不同的二叉树上应用相同的路径，这是行不通的。

所以你可以只保存一个序列，例如一个字符串，例如 "lrllrrr"哪里l表示左分支，r意思是右枝。但是将这些信息存储在字符串中仍然不是很有效。

这可以通过使用 boolean 数组来改进。但我不知道这些在后台的Java中是如何处理的。另外，我想避免固定大小的字符串/数组。

我的下一个想法是直接将路径存储在二进制整数中，例如 0100111 (从左到右阅读)。然后，您可以使用 << 添加“向左移动”并使用<<“向右移动” ，然后是 ++ 。但这种方法有三个缺点:

1. 在 Java 中，没有无符号整数。我对Java中的按位运算符了解不多，所以我想知道如何处理原语int的符号位或long ？
2. 这种表示形式的条目计数受到组成整数的二进制位数的限制(例如 long 为 63)。这可能可以通过使用 BigInteger 来解决.
3. 至少以一个“左”条目开头的路径无法正确存储，因为在处理整数时，默认情况下会忽略最左边的“0”数字。

那么，Java中有没有什么方法可以存储一系列特定的位，以便我可以轻松地单独读取它们？如果这样的东西确实已经存在，我想了解更多关于它是如何实现的。如果 Java 中没有这样的东西，并且它太困难或根本不可能，那么您将如何在另一种环境/另一种语言中实现这一点？

提前致谢。

编辑:'0'数字位于最左边

Answer 1

您可以使用单个整数来表示路径。树的大小增加 1、2、4、8 等

另请注意，在谈论“最小”时，请记住内存块大小限制，并且还要注意您的二叉树可能会比您的路径表示大得多。


0
1 2
3 4 5 6