Python: how to save a binary tree?

Question

I was wondering how to save the binary tree that I created earlier. Does anyone know how to do this? Thank you very much.

PD: There is a link on how to implement a binary tree, I use this pice od code: http://code.activestate.com/recipes/286239-binary-ordered-tree/

Answer 1

One simple solution: - expand the current class to the load and save methods - add a unique identifier to each node - implement it to perform parsing from top to bottom and save each node in xml with a structure like

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

You are done (if the data is easily serialized at least), first the node is your root of the tree.

Do not forget about fertilizer, and your tree will be reborn even more beautiful

Answer 2

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

It may be useful to include markers for each node that indicate whether it is a leaf of the node (which then tells you whether the next element is lower or higher than the current node). Alternatively, you may need to have a marker that indicates a NULL node, which can help, for example, for nodes with a left but not a right branch.

EG:

  A BC DEF 

May be submitted:

 ABD - - E - - C - F - - 

Or how:

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

Reminds me of the computer science homework I did in college.

Answer 3

You can implement a small database (e.g. sqlite3) to maintain the structure.

Example:

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

As with Bruce's answer, you must implement the save / load function.

Answer 4

Another idea:

Binary tree type:

  A / \ BC / \ \ DEF 

May be represented as:

 ABC BDE CF 

Or, more abstractly:

 <parent-id><separator><child-1-id>(<separator><child-2-id>)?<newline> 

It depends on how complex the nodes are. If they are something other than strings, numbers, or logical values, then it is probably easier and faster to simply pickle the whole tree.