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.
__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
__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), ')'])
TreeNode.__repr__ is then really simple, and my class’s
__str__ just returns the node’s
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
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()
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