BFSDFS.py

import sys

def get_breadth_first_nodes(root):
    nodes = []
    stack = [root]
    while stack:
        cur_node = stack[0]
        stack = stack[1:]
        nodes.append(cur_node)
        for child in cur_node.get_children():
            stack.append(child)
    return nodes

def get_depth_first_nodes(root):
    nodes = []
    stack = [root]
    while stack:
        cur_node = stack[0]
        stack = stack[1:]
        nodes.append(cur_node)        
        for child in cur_node.get_rev_children():
            stack.insert(0, child)
    return nodes

########################################################################
class Node(object):
    def __init__(self, id_):
        self.id = id_
        self.children = []
        
    def __repr__(self):
        return "Node: [%s]" % self.id
    
    def add_child(self, node):
        self.children.append(node) 
    
    def get_children(self):
        return self.children         
    
    def get_rev_children(self):
        children = self.children[:]
        children.reverse()
        return children         

########################################################################
def println(text):
    sys.stdout.write(text + "\n")
    
def make_test_tree():
    a0 = Node("a0")
    b0 = Node("b0")      
    b1 = Node("b1")      
    b2 = Node("b2")      
    c0 = Node("c0")      
    c1 = Node("c1")  
    d0 = Node("d0")   
    
    a0.add_child(b0) 
    a0.add_child(b1) 
    a0.add_child(b2)
    
    b0.add_child(c0) 
    b0.add_child(c1) 
    
    c0.add_child(d0)
    
    return a0                  

def test_breadth_first_nodes():
    root = make_test_tree()
    node_list = get_breadth_first_nodes(root)
    for node in node_list:
        println(str(node))

def test_depth_first_nodes():
    root = make_test_tree()
    node_list = get_depth_first_nodes(root)
    for node in node_list:
        println(str(node))

########################################################################
if __name__ == "__main__":
    test_breadth_first_nodes()
    println("")
    test_depth_first_nodes()