[Tutor] Most efficient representation of a tree? [a list representation]

[Daniel Yoo]

On Fri, 4 May 2001, VanL wrote:

> What would be the most efficient representation of a tree? 
> In this tree, each node could have an arbitrary number of children.
> I also wanted to be able to order the children so I can traverse the
> trees in different ways (preorder, postorder, etc).  Anyway, at least a
> leftmost-child, right-sibling ordering.
> 
> I was considering two options:
> 
> 1. A modification of Guido's adjacency-list implementation of a graph
> (see http://www.python.org/doc/essays/graphs.html).  After all, this
> sort of tree is just special case sparse graph.
> 
> 2. A node class with a parent link and a list of links to each child --
> essentially a generalization of the linked list class that I posted here
> a month ago.
> 
> Any other options?

Apologies for the late reply!  


I'm choosing option two: it's fairly easy to work with.  I can put up
sample code that implements this as soon as I get home.


There's another way to do this, of course.  There's a representation of
binary trees that uses flat lists, and this is one is especially cute:

###
def left(index):
    return 2 * index + 1

def right(index):
    return 2 * index + 2

def parent(index):
    return index / 2

def inorder(tree, index):
    """Here's a sample algorithm that uses this tree
       representation.  Inorder traversal."""
    if index >= len(tree):
        return
    inorder(tree, left(index))
    print tree[index]
    inorder(tree, right(index))

def preorder(tree, index):
    if index >= len(tree): return
    print tree[index]
    preorder(tree, left(index))
    preorder(tree, right(index))

if __name__ == '__main__':
    mytree = [1, 2, 3, 4, 5, 6, 7, 8]
    print "Here's an inorder traversal of our mytree."
    inorder(mytree, 0)   ## Start an inorder traversal at the root at 0.
    print
    print "Here's a preorder traversal:"
    preorder(mytree, 0)
###

The idea is to store our data in a list, and to jump around in our tree by
index number.  Getting at our left or right child is simple: we just do a
little arithmetic on our current position.
  
What's particularly interesting is that this representation allows us to
grab the parent of the node really easily.  All of this is done without
explicitily storing left/right references: it's all done with indices, so
it also saves some space, if you're into space efficiency.

Binary trees can represent general trees, so this should be enough to make
a good general tree.


Hope this helps!