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
