Permalink: http://www.treeweb.es/u/1297/
16/10/2015
Traverse trees with Python
#-*- coding: utf-8 -*-
u"""
program3.py
"""
class Tree():
def __init__(self, name=''):
self.name = name
self.children = []
def add(self, node):
return self.children.append(node)
#-*- coding: utf-8 -*-
u"""
program3_test.py
"""
import unittest
from program3 import Tree
def build_tree():
f = Tree('F')
b = Tree('B')
f.add(b)
a = Tree('A')
b.add(a)
d = Tree('D')
b.add(d)
c = Tree('C')
d.add(c)
e = Tree('E')
d.add(e)
g = Tree('G')
f.add(g)
i = Tree('I')
g.add(i)
h = Tree('H')
i.add(h)
return f
def preorder(tree, result=[]):
result.append(tree.name)
for node in tree.children:
preorder(node, result)
return result
def postorder(tree, result=[]):
for node in tree.children:
postorder(node, result)
result.append(tree.name)
return result
def breadth(tree, result=[]):
queue = []
queue.append(tree)
while len(queue) > 0:
node = queue.pop(0)
result.append(node.name)
for node in node.children:
queue.append(node)
return result
class TestProgram3(unittest.TestCase):
def test_check_tree(self):
sample_tree = build_tree()
print 'Preorder:', preorder(sample_tree)
print 'Postorder: ', postorder(sample_tree)
print 'Breadth: ', breadth(sample_tree)
if __name__ == '__main__':
unittest.main()
