Trees

External Interface

• tree CreateEmptyTree ()
  // Create an empty tree

• tree CreateTreeN (labeltype label, tree T1 ... TN)
  // Create a tree with root label and N children T1..TN

• AddRightSubtree (tree subtree, node n)
  // Make subtree the rightmost child of n

• AddLeftSubtree (tree subtree, node n)
  // Make subtree the leftmost child of n

• node Root (tree T)
  // Return the root node of T

• node Parent (node n)
  // Return the parent node of n

• node LeftmostChild (node n)
  // Return the leftmost child node of n

• node RightSibling (node n)
  // Return the right sibling of n

• labeltype Label (node n)
  // Return the label at node n

Implementations

When implementing general trees, we are constrained by the fact that each node may have an arbitrary number of children.

• Array representation: each tree is an array of node records, where each node contains the index of its parent in the array. Index 0 is used to refer to the empty tree.
  • Parent is O(1); moving up the tree from leaf node to root requires time proportional to the height of the tree.
  • Adding subtrees to an existing tree requires copying the tree from one array to another, since trees don't share array space.
  • LeftmostChild and RightSibling are not well defined.
• Arrary with list of siblings representation: each tree is an array of parent nodes, each of which include a list of its children.
  • LeftmostChild and RightSibling are O(1).
  • Parent is O(N), where the tree has N nodes, since we have to search all the lists of childen to find a parent node.
  • As before, trees don't share array space.
• Array of nodes, each of which holds the index of its leftmost child, right sibling, and parent. Every node in every tree is represented by an index into the one array of nodes.
  • LeftmostChild, RightSibling, and Parent are O(1).
  • All trees share array space.
• Same as above, using dynamic allocation for nodes, and pointers (rather than an index) to represent each node.