3.1.1.1. Binary Trees¶

A binary tree is made up of a finite set of nodes that is either empty or consists of a node called the root together with two binary trees, called the left and right subtrees, which are disjoint from each other and from the root.

Notation: Node, children, edge, parent, ancestor, descendant, path, depth, height, level, leaf node, internal node, subtree.

3.1.1.2. A Recursive Data Structure¶

3.1.1.3. Binary Tree Node Class¶

interface BinNode<E> { // Binary tree node ADT
  // Get and set the element value
  public E value();
  public void setValue(E v);

  // return the children
  public BinNode<E> left();
  public BinNode<E> right();

  // return TRUE if a leaf node, FALSE otherwise
  public boolean isLeaf();
}

3.1.1.4. Question¶

• Write a recursive function named count that, given the root to a binary tree, returns a count of the number of nodes in the tree. Function count should have the following prototype:

  int count(BinNode root)
  

3.1.1.5. Traversals¶

• Any process for visiting the nodes in some order is called a traversal.

• Any traversal that lists every node in the tree exactly once is called an enumeration of the tree’s nodes.

• Preorder traversal: Visit each node before visiting its children.

• Postorder traversal: Visit each node after visiting its children.

• Inorder traversal: Visit the left subtree, then the node, then the right subtree.

3.1.1.6. Preorder Traversal (1)¶

static <E> void preorder(BinNode<E> rt) {
  if (rt == null) { return; } // Empty subtree - do nothing
  visit(rt);              // Process root node
  preorder(rt.left());    // Process all nodes in left
  preorder(rt.right());   // Process all nodes in right
}

3.1.1.7. Preorder Traversal (2)¶

Settings

Saving...
Server Error
Resubmit

3.1.1.8. How not to write a traversal¶

// This is a bad idea
static <E> void preorder2(BinNode<E> rt) {
  visit(rt);
  if (rt.left() != null) { preorder2(rt.left()); }
  if (rt.right() != null) { preorder2(rt.right()); }
}

Problems:

1. This has a major bug

2. It puts the focus in the wrong place: Should focus on the current node, not the children. This version is therefore more complicated.

3.1.1.9. Recursion Examples¶

static <E> int count(BinNode<E> rt) {
  if (rt == null) { return 0; }  // Nothing to count
  return 1 + count(rt.left()) + count(rt.right());
}

Settings

Saving...
Server Error
Resubmit

3.1.1.10. Full and Complete Binary Trees¶

Full binary tree: Each node is either a leaf or internal node with exactly two non-empty children.

Complete binary tree: If the height of the tree is \(d\), then all leaves except possibly level \(d\) are completely full. The bottom level has all nodes to the left side.

3.1.1.11. Full Binary Tree Theorem (1)¶

Theorem: The number of leaves in a non-empty full binary tree is one more than the number of internal nodes.

Proof (by Mathematical Induction):

Base case: A full binary tree with 1 internal node must have two leaf nodes.

Induction Hypothesis: Assume any full binary tree T containing \(n-1\) internal nodes has \(n\) leaves.

3.1.1.12. Full Binary Tree Theorem (2)¶

Induction Step: Given tree T with \(n\) internal nodes, pick internal node \(I\) with two leaf children. Remove \(I\)’s children, call resulting tree T’.

By induction hypothesis, T’ is a full binary tree with \(n\) leaves.

Restore \(I\)’s two children. The number of internal nodes has now gone up by 1 to reach \(n\). The number of leaves has also gone up by 1.

3.1.1.13. Full Binary Tree Corollary¶

Theorem: The number of null pointers in a non-empty tree is one more than the number of nodes in the tree.

Proof: Replace all null pointers with a pointer to an empty leaf node. This is a full binary tree.

3.1.1.14. Dictionary¶

/** The Dictionary abstract class. */
public interface Dictionary<K, E> {

  /** Reinitialize dictionary */
  public void clear();

  /** Insert a record
      @param k The key for the record being inserted.
      @param e The record being inserted. */
  public void insert(K key, E elem);

  /** Remove and return a record.
      @param k The key of the record to be removed.
      @return A maching record. If multiple records match
      "k", remove an arbitrary one. Return null if no record
      with key "k" exists. */
  public E remove(K key);

  /** Remove and return an arbitrary record from dictionary.
      @return the record removed, or null if none exists. */
  public E removeAny();

  /** @return A record matching "k" (null if none exists).
      If multiple records match, return an arbitrary one.
      @param k The key of the record to find */
  public E find(K key);

  /** @return The number of records in the dictionary. */
  public int size();
}

3.1.1.15. .¶

.

3.1.1.16. Dictionary (2)¶

• How can we implement a dictionary?

  • We know about array-based lists and linked lists.

  • They might be sorted or unsorted.

  • What are the pros and cons?