Source code online books for professionals by professionals

Figure 2-4.  A sample tree with a highlighted path from the root to a leaf
We could represent that tree with lists of lists, like this:
 
>>> T = [["a", "b"], ["c"], ["d", ["e", "f"]]]
>>> T[0][1]
'b'
>>> T[2][1][0]
'e'
 
Each list is, in a way, a neighbor (or child) list of the anonymous internal nodes. In the second example, we access 
the third child of the root, the second child of that child, and finally the first child of that (path highlighted in the figure).
In some cases, we may know the maximum number of children allowed in any internal node. For example, a 
binary tree is one where each internal node has a maximum of two children. We can then use other representations, 
even objects with an attribute for each child, as shown in Listing 2-7.

---

Chapter 2 
■
 the BasiCs
31
Listing 2-7.  A Binary Tree Class
class Tree:
    def __init__(self, left, right):
        self.left = left
        self.right = right
 
You can use the Tree class like this:
 
>>> t = Tree(Tree("a", "b"), Tree("c", "d"))
>>> t.right.left
'c'
 
You can, for example, use None to indicate missing children, such as when a node has only one child. You are, of 
course, free to combine techniques such as these to your heart’s content (for example, using a child list or child set in 
each node instance).
A common way of implementing trees, especially in languages that don’t have built-in lists, is the “first child, 
next sibling” representation. Here, each tree node has two “pointers,” or attributes referencing other nodes, just like 
in the binary tree case. However, the first of these refers to the first child of the node, while the second refers to its next 
sibling, as the name implies. In other words, each tree node refers to a linked list of siblings (its children), and each 
of these siblings refers to a linked list of its own. (See the “Black Box” sidebar on list, earlier in this chapter, for a brief 
introduction to linked lists.) Thus, a slight modification of the binary tree in Listing 2-7 gives us a multiway tree, as 
shown in Listing 2-8.
Listing 2-8.  A Multiway Tree Class
class Tree:
    def __init__(self, kids, next=None):
        self.kids = self.val = kids
        self.next = next
 
The separate val attribute here is just to have a more descriptive name when supplying a value, such as 'c', 
instead of a child node. Feel free to adjust this as you want, of course. Here’s an example of how you can access this 
structure:
 
>>> t = Tree(Tree("a", Tree("b", Tree("c", Tree("d")))))
>>> t.kids.next.next.val
'c'
 
And here’s what that tree looks like:
The kids and next attributes are drawn as dotted arrows, while the implicit edges of the trees are drawn solid. 
Note that I’ve cheated a bit and not drawn separate nodes for the strings "a", "b", and so on; instead, I’ve treated 
them as labels on their parent nodes. In a more sophisticated tree structure, you might have a separate value field in 
addition to kids, instead of using one attribute for both purposes.
a
b
c
d

---

Chapter 2 
■
 the BasiCs
32
Normally, you’d probably use more elaborate code (involving loops or recursion) to traverse the tree structure 
than the hard-coded path in this example. You’ll find more on that in Chapter 5. In Chapter 6, you’ll also see some 
discussion about multiway trees and tree balancing.