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
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()