Exercises: Tree Data Structures
Feb 262018Before attempting these exercises, you should read the posts about trees, ways to think about trees, and tree data structures.
Exercises

The following Python code represents a tree as a listoflists.
tree = [ 'a', ['b', 'c', ['d', 'e']], 'f', ['g', 'h'] ]
 Draw a node/link diagram for the tree.
 Find
tree[1]
,tree[1][2]
andtree[1][2][0]
.  Write code to access the node with the value
'h'
.  Draw a second node/link diagram showing the state of the tree after
tree[3].append(['i', 'j', 'k'])
is executed.
 The following Python code declares the
Node
class, and constructs a tree using the listofchildren 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') ]) ])
 Draw a node/link diagram for the tree.
 Find
root.children[0]
androot.children[0].value
.  Write code to access the node with value
'g'
.  Draw a second node/link diagram showing the state of the tree after
root.children.append(Node('h'))
is executed.
 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]
 Draw a node/link diagram for the tree.
 Find
f.parent.value
andf.parent.parent.value
.  Draw a boxandpointer diagram for the tree.
Include only the
PPNode
objects in your diagram; you do not need to show the variables or thenodes
list.
 Consider the following tree, given as a node/link diagram:
 Represent this tree using the listofchildren data structure, with the
Node
class.  Use the
PPNode
class to represent it as a parent pointer tree.
 Represent this tree using the listofchildren data structure, with the
There are no published comments.