Python tree implementation

Thursday 3rd of July 2014 03:07:49 PM


  Toggle Advanced Options



Update, May 03, 2014:

I've added app.py (and the accompanying execution output) to clarify how to use the Tree class. Furthermore, I have refactored the Tree class to use a dictionary to hold the nodes instead of a list which dramatically increases the class's performance. Finally, I also cleaned up the code a bit with regards to variable and method naming.

For the sake of comparison, check out the equivalent Java tree implementation.

Source code



Output (from running app.py)

/Library/Frameworks/Python.framework/Versions/3.4/bin/python3 .../app.py

Harry
     Jane
         Joe
         Diane
             George
                 Jill
                     Carol
             Mary
         Mark
     Bill
         Grace
***** DEPTH-FIRST ITERATION *****
Harry
Jane
Joe
Diane
George
Jill
Carol
Mary
Mark
Bill
Grace
***** BREADTH-FIRST ITERATION *****
Harry
Jane
Bill
Joe
Diane
Mark
Grace
George
Mary
Jill
Carol

Process finished with exit code 0

app.py

# Copyright (C) by Brett Kromkamp 2011-2014 (brett@youprogramming.com)
# You Programming (http://www.youprogramming.com)
# May 03, 2014

from tree import Tree

(_ROOT, _DEPTH, _BREADTH) = range(3)

tree = Tree()

tree.add_node("Harry")  # root node
tree.add_node("Jane", "Harry")
tree.add_node("Bill", "Harry")
tree.add_node("Joe", "Jane")
tree.add_node("Diane", "Jane")
tree.add_node("George", "Diane")
tree.add_node("Mary", "Diane")
tree.add_node("Jill", "George")
tree.add_node("Carol", "Jill")
tree.add_node("Grace", "Bill")
tree.add_node("Mark", "Jane")

tree.display("Harry")
print("***** DEPTH-FIRST ITERATION *****")
for node in tree.traverse("Harry"):
    print(node)
print("***** BREADTH-FIRST ITERATION *****")
for node in tree.traverse("Harry", mode=_BREADTH):
    print(node)

node.py

# Copyright (C) by Brett Kromkamp 2011-2014 (brett@youprogramming.com)
# You Programming (http://www.youprogramming.com)
# May 03, 2014

class Node:
    def __init__(self, identifier):
        self.__identifier = identifier
        self.__children = []

    @property
    def identifier(self):
        return self.__identifier

    @property
    def children(self):
        return self.__children

    def add_child(self, identifier):
        self.__children.append(identifier)

tree.py

# Brett Kromkamp (brett@youprogramming.com)
# You Programming (http://www.youprogramming.com)
# May 03, 2014

from node import Node

(_ROOT, _DEPTH, _BREADTH) = range(3)


class Tree:

    def __init__(self):
        self.__nodes = {}

    @property
    def nodes(self):
        return self.__nodes

    def add_node(self, identifier, parent=None):
        node = Node(identifier)
        self[identifier] = node

        if parent is not None:
            self[parent].add_child(identifier)

        return node

    def display(self, identifier, depth=_ROOT):
        children = self[identifier].children
        if depth == _ROOT:
            print("{0}".format(identifier))
        else:
            print("t"*depth, "{0}".format(identifier))

        depth += 1
        for child in children:
            self.display(child, depth)  # recursive call

    def traverse(self, identifier, mode=_DEPTH):
        # Python generator. Loosly based on an algorithm from 
        # 'Essential LISP' by John R. Anderson, Albert T. Corbett, 
        # and Brian J. Reiser, page 239-241
        yield identifier
        queue = self[identifier].children
        while queue:
            yield queue[0]
            expansion = self[queue[0]].children
            if mode is _DEPTH:
                queue = expansion + queue[1:]  # depth-first
            elif mode is _BREADTH:
                queue = queue[1:] + expansion  # width-first

    def __getitem__(self, key):
        return self.__nodes[key]

    def __setitem__(self, key, item):
        self.__nodes[key] = item



PerfectLearn Knowledge Management World War 2 (History) Case Study



YouProgramming Programming Tutorials YouTube Channel



  • YouProgramming, a website and accompanying YouTube channel with video tutorials and courses related to the Java and Python programming languages. With these tutorials I hope to teach you the art of software development in general and Java, Android, and Python development in particular.






Google