Serialize and deserialize a tree

Question

Suppose each node of a tree has maximum n children. I want to serialize and de-serialize for a tree. My current solution is doing pre-order traverse, and using # to represent None child.

I'm wondering if there are any better implementation method. My current concern for my code is if the tree has too many None node (kinds of sparse tree), there will be a lot # in the serialized string output. But I have not figured out a way to represent serialized tree better, since I think for None node, we still need some kinds of information to represent there is an empty node there.

I'm looking forward to any smart ideas on existing code and smart ideas to represent serialized tree in a better (more compact and more efficient -- for both serialize and de-serialize).

My print tree method is just for the purpose of verification. deserialize is correctly re-constructing the tree, so we can skip code review for this part.

number_of_children = 3
index = 0
class Node:
 def __init__(self, value):
 self.value = value
 self.children = [] # a list of Node
 def serialize(self, result): # serialzie a tree into a string
 result.append(str(self.value))
 for child in self.children:
 if child:
 child.serialize(result)
 else:
 result.append('#')
 def printTree(self): # print tree layer by layer
 current_level_buffer=[]
 current_level_buffer.append(self)
 current_level_count = 1
 next_level_count=0
 next_level_buffer=[]
 print_buffer=[]
 next_level_valid = 1
 while True:
 node = current_level_buffer.pop(0)
 if not node:
 print_buffer.append('#')
 current_level_count -= 1
 else:
 print_buffer.append(str(node.value))
 current_level_count -= 1
 for child in node.children:
 next_level_buffer.append(child)
 next_level_count += 1
 if child:
 next_level_valid += 1
 if current_level_count == 0:
 print ' '.join(print_buffer)
 current_level_count = next_level_count
 current_level_buffer = next_level_buffer
 next_level_count = 0
 next_level_buffer=[]
 print_buffer=[]
 if next_level_valid == 0:
 return
 next_level_valid = 0
def deserialize(source): # deserialize a string into a tree
 global index
 current_node = None
 if source[index] != '#':
 current_node = Node(source[index])
 for i in range(number_of_children):
 index += 1
 current_node.children.append(deserialize(source))
 return current_node
if __name__ == "__main__":
 root = Node(0)
 child11 = Node(1)
 child12 = Node(2)
 root.children.append(child11)
 root.children.append(child12)
 root.children.append(None)
 child21 = Node(3)
 child22 = Node(4)
 child23 = Node(5)
 child11.children.append(child21)
 child11.children.append(child22)
 child11.children.append(child23)
 child24=Node(6)
 child25=Node(7)
 child26=Node(8)
 child12.children.append(child24)
 child12.children.append(child25)
 child12.children.append(child26)
 leafnodes = [child21, child22, child23, child24, child25, child26]
 for leaf in leafnodes:
 leaf.children.append(None)
 leaf.children.append(None)
 leaf.children.append(None)
 root.printTree()
 result = []
 root.serialize(result)
 print result
 print ''.join(result)
 new_root = deserialize(''.join(result))
 new_root.printTree()

Answer 1

Your printTree function is unnecessarily long.

Also, I really don't like the output of your serialize. I was not able to parse (as a human) this back into the structure of the tree. For me it would be much better if the structure was apparent from the serialization.

Therefore I rewrote your code in the following way:

class Node:
 def __init__(self, value='#', children=None):
 self.value = value
 self.children = children if children else []
 def __nonzero__(self):
 return self.value != '#'
 def __eq__(self, other):
 return self.value == other.value and self.children == other.children
 def __str__(self):
 buf, out = [self], []
 while buf:
 # current level
 out.append(", ".join(str(node.value) for node in buf))
 if any(node for node in buf):
 # add children
 buf = [subnode if subnode else Node()
 for node in buf
 for subnode in node.children]
 else:
 break
 return "\n".join(out)
 def __repr__(self):
 if not self:
 return "Node()"
 children_repr = ",".join(repr(child) for child in self.children)
 return "Node({.value},[{}])".format(self, children_repr)
 def serialize(self):
 return repr(self).replace("Node", "").replace("()", "#")
 @staticmethod
 def deserialize(source):
 return eval(source.replace("#", "()").replace("(", "Node("))
if __name__ == "__main__":
 root = Node(1, [Node(2, [Node(4)]), Node(3, [Node(5), Node(6)])])
 print repr(root)
 print root
 source = root.serialize()
 root2 = Node.deserialize(source)
 print repr(root2)
 print root2
 assert root == root2

This class has the nice feature, that eval(repr(root)) is a copy of root, so repr(root) is a serialization of root.

The output of repr(root) is a bit verbose, though:

Node(1,[Node(2,[Node(4,[])]),Node(3,[Node(5,[]),Node(6,[])])])

Therefore I defined a serialize function, which just gets rid of all the Nodes. The deserialize function just puts them back in and does an eval.

Note that I used a different tree here than you. Here would be your structure:

root = Node(0, [Node(1, [Node(3, [Node(), Node(), Node()]),
 Node(4, [Node(), Node(), Node()]),
 Node(5, [Node(), Node(), Node()])]),
 Node(2, [Node(6, [Node(), Node(), Node()]),
 Node(7, [Node(), Node(), Node()]),
 Node(8, [Node(), Node(), Node()])]),
 Node()])

Or, even better to visualize:

root = Node(0, [Node(1, [Node(3, [Node(),
 Node(),
 Node()]),
 Node(4, [Node(),
 Node(),
 Node()]),
 Node(5, [Node(),
 Node(),
 Node()])]),
 Node(2, [Node(6, [Node(),
 Node(),
 Node()]),
 Node(7, [Node(),
 Node(),
 Node()]),
 Node(8, [Node(),
 Node(),
 Node()])]),
 Node()])

Example:

>>> root.serialize()
'(0,[(1,[(3,[#,#,#]),(4,[#,#,#]),(5,[#,#,#])]),(2,[(6,[#,#,#]),(7,[#,#,#]),(8,[#,#,#])]),#])'

This could be cut down even further, but at this point it becomes a balance between the processing time needed to make this string smaller and the gain in memory from that.

With this function it could become:

def serialize2(self):
 replacements = [("Node", ""), ("()", "#"),
 ("(", ""), (")", ""), (",[", "["), (",", "")]
 out = repr(self)
 for replacement in replacements:
 out = out.replace(*replacement)
 return out
>>> root.serialize2()
'0[1[3[###]4[###]5[###]]2[6[###]7[###]8[###]]#]'

But this becomes hard to parse back into the tree and would break the setup of using __repr__ and eval. It would be possible using some fancy regular expressions, though.

• Graipher: @LinMa Yeah, I was thinking of that. It would be sufficient for my code to have () represent a completely empty node. It makes the repr function slightly more complicated, but it might be worth it.
• Graipher: @LinMa In my opinion repr is a lot more general than a specialized serialize. Which is why the latter is just a special case of the former in my code.
• Graipher: @LinMa It is for representation (i.e.representing the total structure of the object). Ideally it is represented in such a way that eval(repr(object)) works, which it is here.
• Graipher: @LinMa In this version of my code, the empty node is still Node('#', []) in repr, while Node() would be enough. Working on a streamlining of this, where the serialized string is less than half the length of this one.
• Graipher: @LinMa str.format can do a limited number of operations, namely attribute access and indexing: x = [1, 2, 3]; "{0[1]}".format(x); "{[1]}".format(x); "{x[1]}".format(x=x) all return 2. Similarly my code prints self.value with "{.value}".format(self).