Я пытаюсь сохранить бинарный путь настолько эффективным, насколько это возможно (с точки зрения использования как можно меньшего количества памяти / возможности). Путь, который ведет к указанному c узлу в связанном двоичном дереве (например, начиная с root). Простой способ сохранить это - сохранить сами узлы (или их значения).
Но это не эффективно и не элегантно. Если я хочу применить один и тот же путь к другому BinaryTree, это не работает.
Таким образом, вы можете сохранить только последовательность, например строку, например "lrllrrr", где l означает левую ветвь, r означает правую ветвь. Но хранение этой информации в строке все еще не очень эффективно.
Это можно улучшить, используя массив логических значений. Но я не знаю, как они обрабатываются в Java в фоновом режиме. Кроме того, я хотел бы избегать строк / массивов фиксированного размера.
Моя следующая идея состояла в том, чтобы напрямую сохранить путь в двоичном целом числе, например 0100111 (чтение слева направо). Затем можно добавить «движение влево» с помощью << и «движение вправо» с помощью <<, за которым следует ++. Но у этого подхода есть три недостатка:
- В Java нет целых чисел без знака. Я не очень разбираюсь в побитовых операторах в Java, поэтому мне интересно, как работать со знаковым битом примитива
int или long? - Количество записей такого представления ограничено количеством двоичных цифр, составляющих целое число (например, 63 для
long). Вероятно, это можно решить с помощью BigInteger. - . Путь, начинающийся хотя бы с одной «левой» записи, не может быть сохранен правильно, поскольку цифры «0» в левой части по умолчанию игнорируются при работе с целые числа.
Итак, есть ли в Java какой-либо способ сохранить определенную c серию битов, чтобы я мог читать их по отдельности без особых усилий? Если что-то подобное уже существует, я бы хотел больше узнать о том, как оно реализовано. Если в Java такого нет, и это слишком сложно или просто невозможно, как бы вы подошли к этому в другой среде / на другом языке?
Заранее спасибо.
РЕДАКТИРОВАТЬ : цифры '0' слева