CS 245 Lecture 23 – Tree Edits and Traversals
Deprecated: ltrim(): Passing null to parameter #1 ($string) of type string is deprecated in /var/www/twodee/blog/wp-includes/wp-db.php on line 3030
Deprecated: parse_str(): Passing null to parameter #1 ($string) of type string is deprecated in /var/www/twodee/blog/wp-content/plugins/jetpack/class.jetpack.php on line 4255
Deprecated: Creation of dynamic property Jetpack_Carousel::$localize_strings is deprecated in /var/www/twodee/blog/wp-content/plugins/jetpack/modules/carousel/jetpack-carousel.php on line 339
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
It all starts simple
Young eyes see just black and white
We gray as we age
Young eyes see just black and white
We gray as we age