serialize_deserialize_nary_tree.py

import Queue
class AbNode(object):
    def __init__(self, d):
        self.data = d
        self.children = []
 
 
def serial_bfs(node):
    vals = []
    q = Queue.Queue()
    q.put(node)
    vals.append(node.data)
    while not q.empty():
        nd = q.get(timeout=1)
        for child in nd.children:
            q.put(child)
            vals.append(child.data)
       
        vals.append('#')
           
    return vals
 
def deserial_bfs(data):
    q = Queue.Queue()
    di = iter(data)
    node = AbNode(di.next())
    res = node
    for val in di:
        if val != '#':
            child = AbNode(val)
            node.children.append(child)
            q.put(child)
        elif not q.empty():
            node = q.get(timeout=1)
           
    return res
 
if __name__ == '__main__':
 
# 1 is the root
# 1's children: 2
# 2's children: 34
# 4's children: 56
# 6's children: 78
    a = AbNode(1)
    b = AbNode(2)
    c = AbNode(3)
    d = AbNode(4)
    e = AbNode(5)
    f = AbNode(6)
    g = AbNode(7)
    h = AbNode(8)
    f.children = [g,h]
    d.children = [e,f]
    b.children = [c,d]
    a.children = [b]
    print serial_bfs(a)
    print serial_bfs(deserial_bfs(serial_bfs(a)))