#python #persistence #binary-tree
#python #постоянство #binary-tree
Вопрос:
Мне было интересно, как сохранить двоичное дерево, которое я ранее создал. Кто-нибудь знает, как это сделать? Большое вам спасибо.
PD: Здесь есть ссылка о том, как реализовать двоичное дерево, я использую этот фрагмент кода:http://code.activestate.com/recipes/286239-binary-ordered-tree /
Комментарии:
1. Вы хотели бы, чтобы структура и данные внутри были записаны на жесткий диск?
2. … Опять же, вы могли бы просто рассолить это.
3. @fuggle: Да, я хочу сохранить данные моего дерева на моем жестком диске.
Ответ №1:
Одно простое решение: — расширить текущий класс, чтобы иметь метод load and save — добавить уникальный идентификатор к каждому узлу — реализовать синтаксический анализ сверху вниз и сохранить каждый узел в xml со структурой, подобной этой
<node id="mynicelycrafteduniqueid">
<data>...</data>
<leftChild>childuniqueId</leftChild>
<rightChild/> <!-- no right child -->
</node>
Вы закончили (если данные, по крайней мере, легко сериализуются), первый узел — это корень вашего дерева.
не забывайте удобрения, и ваше дерево возродится еще более красивым
Комментарии:
1. Как насчет сохранения моих xml-структур в текстовом файле? Есть что-то лучше, чем сохранять их в текстовом файле?
Ответ №2:
Существуют разные типы двоичных деревьев с разными правилами, которые могут помочь упростить десериализацию, но в принципе, просто пройдитесь по дереву и выведите каждый узел по порядку, чтобы затем воссоздать его, прочитать в вашем файле и восстановить структуру.
Может быть полезно включить маркеры для каждого узла, которые указывают, является ли это конечным узлом (которые затем сообщают вам, принадлежит ли следующий элемент ниже или выше текущего узла. В качестве альтернативы, вы можете захотеть иметь маркер, который указывает нулевой узел, что может помочь, например, для узлов с левой, но не правой ветвью.
НАПРИМЕР:
A
B C
D E F
Может быть представлено:
A B D - - E - - C - F - -
Или как:
A[B[D,E],C[-,F]]
Напоминает мне домашнее задание по информатике, которое я делал в колледже.
Комментарии:
1. если дерево не сбалансировано, это может привести к интенсивному потреблению пустого пространства (2 ^max_depth_of_tree). Однако ваше решение хорошо для сбалансированного дерева, поскольку позиционирование узла неявно при чтении, нет необходимости отслеживать идентификаторы
2. Да, это то, что я имел в виду вверху о различных типах двоичных деревьев. Вы должны учитывать свой конкретный вариант использования, если хотите придумать что-то эффективное.
Ответ №3:
Вы могли бы реализовать небольшую базу данных (такую как sqlite3), чтобы сохранить структуру.
Пример:
Node: {nodeId(PK), [leftChildId](FK), [rightChildId](FK)}
leftChildId, rightChildId references Node;
Аналогично ответу Брюса, вы бы реализовали функцию save / load .
Ответ №4:
Еще одна идея:
Двоичное дерево, подобное:
A
/
B C
/
D E F
Может быть представлено как:
A B C
B D E
C F
Или, более абстрактно:
<parent-id><separator><child-1-id>(<separator><child-2-id>)?<newline>
Это зависит от того, насколько сложны узлы. Если они представляют собой что-либо иное, чем строки, числа или логические значения, вероятно, проще и быстрее просто удалить все дерево.
Комментарии:
1. Мне нравится ваш способ, но мне нужно сохранить содержимое каждого узла, а не только его идентификатор.
2. Возможно, аналогичный формат:
<parent-content><separator><child-1-id>(<separator><child-2-id>)?<newline>, где строка содержимого содержит идентификатор.