DS&A

Exercises: Tree Data Structures

Before attempting these exercises, you should read the posts about trees, ways to think about trees, and tree data structures.

Exercises

1. The following Python code represents a tree as a list-of-lists.

   tree = [
       'a',
       ['b', 'c', ['d', 'e']],
       'f',
       ['g', 'h']
   ]

   1. Draw a node/link diagram for the tree.
   2. Find tree[1], tree[1][2] and tree[1][2][0].
   3. Write code to access the node with the value 'h'.
   4. Draw a second node/link diagram showing the state of the tree after tree[3].append(['i', 'j', 'k']) is executed.
2. The following Python code declares the Node class, and constructs a tree using the list-of-children data structure.

   class Node:
       def __init__(self, value, children=None):
           self.value = value
           self.children = children
       
       def __repr__(self):
           if self.children:
               fmt = 'Node({!r}, {!r})'
           else:
               fmt = 'Node({!r})'
           return fmt.format(self.value, self.children)
   
   root = Node('a', [
       Node('b', [
           Node('c')
       ]),
       Node('d'),
       Node('e', [
           Node('f'),
           Node('g')
       ])
   ])

   1. Draw a node/link diagram for the tree.
   2. Find root.children[0] and root.children[0].value.
   3. Write code to access the node with value 'g'.
   4. Draw a second node/link diagram showing the state of the tree after root.children.append(Node('h')) is executed.
3. The following Python code declares the PPNode class, and constructs a tree using the parent pointer tree data structure.

   class PPNode:
       def __init__(self, parent, value):
           self.parent = parent
           self.value = value
       
       def __repr__(self):
           fmt = 'PPNode({!r}, {!r})'
           return fmt.format(self.parent, self.value)
   
   a = PPNode(None, 'a')
   b = PPNode(a, 'b')
   c = PPNode(a, 'c')
   d = PPNode(b, 'd')
   e = PPNode(b, 'e')
   f = PPNode(c, 'f')
   g = PPNode(c, 'g')
   h = PPNode(f, 'h')
   
   nodes = [a, b, c, d, e, f, g, h]

   1. Draw a node/link diagram for the tree.
   2. Find f.parent.value and f.parent.parent.value.
   3. Draw a box-and-pointer diagram for the tree. Include only the PPNode objects in your diagram; you do not need to show the variables or the nodes list.
4. Consider the following tree, given as a node/link diagram:

   

   1. Represent this tree using the list-of-children data structure, with the Node class.
   2. Use the PPNode class to represent it as a parent pointer tree.

• Tags: 
• exercises, trees, data structures