Python: how to save a Binary Tree?

Question

I was wondering how to save a Binary Tree that I have previously created. Does anyone know how to do it? Thank you so much.

PD: Here there is a link about how to implement a binary tree, I am using this pice od code: http://code.activestate.com/recipes/286239-binary-ordered-tree/

Answer 1

One easy solution: - extend the current class to have a load and save method - add a unique id to each node - implement to do a top down parsing and save each node to a xml with a structure like that

<node id="mynicelycrafteduniqueid">
    <data>...</data>
    <leftChild>childuniqueId</leftChild>
    <rightChild/> <!-- no right child -->
</node>

You're done (if data is easily serialized at least), first node is your tree root.

don't forget fertilizer and your tree will be reborn even more beautiful

Answer 2

You could implement a small database (such as sqlite3) to have the structure persist.

Example:

Node: {nodeId(PK), [leftChildId](FK), [rightChildId](FK)}
leftChildId, rightChildId references Node;

Similarly to Bruce's answer, you would implement a save / load function.

Answer 3

There are different types of binary trees with different rules that can help simplify deserialization, but basically, just walk the tree and output each node in order, then to re-create it, read in your file and regenerate the structure.

It may be helpful to include markers for each node that indicate whether it's a leaf node (which then tell you whether or not the next element belongs below or above the current node. Alternately, you may want to have a marker that indicates a NULL node, which might help for nodes with a left but not a right branch, for example.

EG:

   A
 B   C
D E    F

Could be represented:

A B D - - E - - C - F - -

Or as:

A[B[D,E],C[-,F]] 

Reminds me of the Computer Science homework I did back in college.