Binary Trees

External Interface

• tree CreateEmptyTree ()
  // Create an empty binary tree

• tree CreateTree (labeltype label, tree T1, tree T2)
  // Create tree with root label, left child T1, right child T2

• MakeLeftChild (tree child, tree T)
  // Make child the left subtree of T

• MakeRightChild (tree child, tree T)
  // Make child the right subtree of T

• tree LeftChild (tree T)
  // Return the left subtree of T

• tree RightChild (tree T)
  // Return the right subtree of T

• labeltype Label (tree T)
  // Return the label at root of T

Implementations

• Array of nodes, each of which holds the index of its left and right child.

• Same as above, using dynamic allocation for nodes, and pointers (rather than an index) to represent each node.