teaching machines

CS 245 Lecture 23 – Tree Edits and Traversals

April 22, 2014 by Chris Johnson. Filed under cs245, lectures, spring 2014.

Agenda

• what ?s
• the uses of trees
• think about this
• adding elements
• removing elements
• traversing

TODO

• Start preassignment 3. Due before May 9.

Think About This

File hierarchy starting at directory 00.

What is printed by the following code?

Stack<File> dirs = new Stack<File>();
dirs.push(new File("00"));
while (!dirs.isEmpty()) {
  File dir = dirs.pop();
  System.out.println(dir);
  for (File child : dir.listFiles()) {
    if (child.isDirectory()) {
      dirs.push(child);
    }
  }
}

What’s printed if we replace Stack with Queue, push with enqueue, and pop with dequeue?

Code

BinarySearchTree.java

package lecture23;

public class BinarySearchTree<K extends Comparable<K>, V> {
  private Node<K, V> root;
  private int size;

  public BinarySearchTree() {
    root = null;
    size = 0;
  }

  public int size() {
    return size(root);
  }

  private int size(Node<K, V> root) {
    if (root == null) {
      return 0;
    } else {
      return 1 + size(root.left) + size(root.right);
    }
  }

  public void add(K key,
                  V value) {
    Node<K, V> nodeToAdd = new Node<K, V>(key, value, null, null);
    if (root == null) {
      root = nodeToAdd;
    } else {
      root.add(nodeToAdd);
    }
    ++size;
  }
  
  public void traverse() {
    postOrderTraverse(root);
  }
  
  private void traverse(Node<K, V> root) {
    if (root == null) {
      return;
    }
    
    traverse(root.left);
    System.out.println(root.key + " -> " + root.value);
    traverse(root.right);
  }
  
  private void preOrderTraverse(Node<K, V> root) {
    if (root == null) {
      return;
    }
    
    System.out.println(root.key + " -> " + root.value);
    traverse(root.left);
    traverse(root.right);
  }
  
  private void postOrderTraverse(Node<K, V> root) {
    if (root == null) {
      return;
    }
    
    traverse(root.left);
    traverse(root.right);
    System.out.println(root.key + " -> " + root.value);
  }

  private static class Node<K extends Comparable<K>, V> {
    private K key;
    private V value;
    private Node<K, V> left;
    private Node<K, V> right;

    public Node(K key,
                V value,
                Node<K, V> left,
                Node<K, V> right) {
      this.key = key;
      this.value = value;
      this.left = left;
      this.right = right;
    }

    public void add(Node<K, V> nodeToAdd) {
      int order = key.compareTo(nodeToAdd.key);
      // if order < 0, then nodeToAdd > current
      // if order > 0, then nodeToAdd < current
      // if order == 0, then nodeToAdd == current

      // Someone is updating an existing node.
      if (order == 0) {
        value = nodeToAdd.value;
      } else if (order < 0) {
        if (right == null) {
          right = nodeToAdd;
        } else {
          right.add(nodeToAdd);
        }
      } else {
        if (left == null) {
          left = nodeToAdd;
        } else {
          left.add(nodeToAdd);
        }
      }
    }
  }
}

BSTBFF.java

package lecture23;

public class BSTBFF {
  public static void main(String[] args) {
    BinarySearchTree<String, String> turtleMap = new BinarySearchTree<String, String>();
    turtleMap.add("Sheldon", "sea turtle");
    turtleMap.add("Squirtle", "Pokemon");
    turtleMap.add("Crush", "box turtle");
    turtleMap.add("Franklin", "eastern spiny soft-shell turtle");
    turtleMap.add("Raphael", "eastern river cooter");
    turtleMap.add("Donatello", "ninja turtle");
    
    turtleMap.traverse();
  }
}

Haiku