Python arborealis

I’ve been implementing a k-ary circularly linked tree (that is, a tree where each node could have a previous, a next, an up, or a down node) in Python.

The page Trees – How to Think Like a Computer Scientist is a nice introduction to some of the background concepts.

To __init__ each node of my TreeNode class you just need to provide the node’s contents and its links

class TreeNode:
    
    def __init__(self,
                 body=None,
                 Prev=None,
                 Next=None,
                 Up=None,
                 Down=None):
        self.body = body
        self.Prev = Prev
        self.Next = Next
        self.Up = Up
        self.Down = Down

I thought hard about getting __repr__ and __str__ right for this class (see Built-in Functions – repr, for example), but __repr__ is a bit tricky if you want to avoid too much recursion. I wrote a small getRepr function for doing this on any class. Members that are instances of the parent are recursed to a depth of one.

def getRepr(self,
            depth=0):
    keys = list(self.__dict__.keys())
    keys.sort()

    fields = []

    for key in keys:

        if (isinstance(self.__dict__[key], self.__class__)):

            if (depth < 1):
                value = getRepr(self.__dict__[key], depth=depth+1)
            else:
                value = ''.join(['<',
                                 self.__class__.__name__,
                                 '(...)>'])

        else:
            value = str(self.__dict__[key])

        fields.append(''.join([key,
                               '=',
                               value]))

    return ''.join([self.__class__.__name__,
                    '(',
                    ', '.join(fields),
                    ')'])

Hence my TreeNode.__repr__ is then really simple, and my class’s __str__ just returns the node’s body

    def __repr__(self):
        return getRepr(self)

    def __str__(self):
        return str(self.body)

Traversing a node goes all the way down to the tip of each branch and then backtracks to the point that a sibling exists. By default my traverse method processes each node in print mode.

    def isLeaf(self):
        return (self.Down is None)

    def traverse(self,
                 process_node=None):
        depth = 0
        node = self

        while (node is not None):

            if (process_node is None):
                import sys
                sys.stdout.write(' '*depth*2 + str(node) + '\n')
            else:
                process_node(node)

            if (node.isLeaf()):
            
                while (node is not None and
                       node != self and
                       node.Next is None):
                    node = node.Up
                    depth = depth - 1

                if (node is None or
                    node == self):
                    break

                node = node.Next
            else:
                node = node.Down
                depth = depth + 1

When it comes to actually populating a tree, my specific application is unusual in that I have a tree already, which is output by an external C program. So I currently have no functions for creating (or deleting) trees – I just read in my external tree from a file and set the links for each node accordingly. As an example (albeit somewhat clunky) of setting up a small tree directly, here’s the tree for the pseudocode 7 = 1 + 2 * 3; end (with the correct operator precedence!)

root = TreeNode()
asgn = TreeNode('=')
root.Down = asgn; asgn.Up = root
lhs = TreeNode(7)
asgn.Down = lhs; lhs.Up = asgn
plus = TreeNode('+')
lhs.Next = plus; plus.Prev = lhs; plus.Up = asgn
one = TreeNode(1)
plus.Down = one; one.Up = plus
times = TreeNode('*')
one.Next = times; times.Prev = one; times.Up = plus
two = TreeNode(2)
times.Down = two; two.Up = times
three = TreeNode(3)
two.Next = three; three.Prev = two; three.Up = times
end = TreeNode('end')
asgn.Next = end; end.Prev = asgn
print(repr(root))
root.traverse()

giving

TreeNode(Down=TreeNode(Down=<TreeNode(...)>, Next=<TreeNode(...)>, Prev=None, Up=<TreeNode(...)>, body==),
  Next=None, Prev=None, Up=None, body=None)
None
  =
    7
    +
      1
      *
        2
        3
  end

Source code: https://github.com/matcross/blog/tree/master/python-arborealis

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: