Jupyter at Bryn Mawr College
Public notebooks: /services/public/dblank / CS206 Data Structures / 2016-Spring / Notebooks

1. Family Tree

The Family Tree is also a recursive data structure.

class FamilyTree {
    String name;
    FamilyTree mother;
    FamilyTree father;
    
    FamilyTree(String name) {
        this.name = name;
    }
    
}

|  Added class FamilyTree

FamilyTree me = new FamilyTree("Doug");

|  Added variable me of type FamilyTree with initial value FamilyTree@44e81672

me.mother = new FamilyTree("Norma");
me.father = new FamilyTree("Scotty");

|  Expression value is: FamilyTree@6aceb1a5
|    assigned to temporary variable $3 of type FamilyTree

|  Expression value is: FamilyTree@ba4d54
|    assigned to temporary variable $4 of type FamilyTree

FamilyTree@ba4d54

System.out.println(me.name);

Doug

System.out.println(me.father.name);

Scotty

1.1 Binary Trees

The data structure. We'll use this the same way that we did the LinkedList. That is we will have:

• Node class - keeps track of next, and data
• A BinaryTree class - has all methods, and head

For BinaryTrees we will use the terms left and right instead of next, and root instead of head.

class Node {
    double data;
    Node left;
    Node right;

    Node(double data) {
        this.data = data;
    }
}

class BinaryTree {
    Node root;

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            ///
        }
    }
}

Consider adding the method add(Node) that would add nodes in no particular order. My natural instincts tell me to let the node do it:

class BinaryTree {
    Node root;

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }
}

...and then have Node do it recursively... but...

class Node {
    double data;
    Node left;
    Node right;

    Node(double data) {
        this.data = data;
    }

    public void add(Node node) {
        if (left == null)
            left = node;
        else if (right == null)
            right = node;
        else {
            /// what would go here?
        }
    }
}

import java.lang.Math;

class Node {
    double data;
    Node left;
    Node right;
    
    Node(double data) {
        this.data = data;
    }
    
    public void add(Node node) {
        if (left == null)
            left = node;
        else if (right == null)
            right = node;
        else {
            if (Math.random() < .5) {
                left.add(node);
            } else {
                right.add(node);
            }
                
        }
    
    }
    
}

|  Added class Node

class BinaryTree {
    Node root;
    
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }
}

|  Added class BinaryTree

BinaryTree btree = new BinaryTree();

|  Added variable btree of type BinaryTree with initial value BinaryTree@2471cca7

btree.add(new Node(23));

btree.add(new Node(46));

How can we get some feedback about what is in the tree? We could print out the tree, but that is actually a bit difficult. Why?

First, let's find the "depth" of the tree:

class BinaryTree {
    Node root;
    
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }
    
    public int depth() {
        return depth(root);
    }
    
    public int depth(Node node) {
        if (node == null) {
            return 0;
        } else {
            return 1 + Math.max(depth(node.left), depth(node.right));
        }
    }
}

|  Replaced class BinaryTree
|    Update replaced variable btree, reset to null
|    Update overwrote class BinaryTree

BinaryTree btree = new BinaryTree();

|  Modified variable btree of type BinaryTree with initial value BinaryTree@50675690

btree.depth()

|  Expression value is: 0
|    assigned to temporary variable $15 of type int

0

btree.add(new Node(23));

btree.depth()

|  Expression value is: 1
|    assigned to temporary variable $17 of type int

1

btree.add(new Node(46));

btree.depth()

|  Expression value is: 2
|    assigned to temporary variable $19 of type int

2

btree.add(new Node(47));
btree.depth()

|  Expression value is: 2
|    assigned to temporary variable $21 of type int

2

btree.add(new Node(47));
btree.depth()

|  Expression value is: 3
|    assigned to temporary variable $23 of type int

3

BinaryTree btree = new BinaryTree();

|  Modified variable btree of type BinaryTree with initial value BinaryTree@5f150435

for (int i=0; i < 1000000; i++) {
    btree.add(new Node(i));
}

What do you think the depth is?

btree.depth();

btree.depth();

|  Expression value is: 23
|    assigned to temporary variable $29 of type int

23

Lab 3: Sorted Binary Tree

Recursive version of add

class Node {
    double data;
    Node left;
    Node right;
    
    Node(double data) {
        this.data = data;
    }
    
    public void add(Node node) {
        if (node.data < this.data) {
            if (this.left == null) {
                this.left = node;
            } else {
                this.left.add(node);
            }
        } else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }
}

|  Modified class Node
|    Update overwrote class Node

class BinaryTree {
    Node root;
    
    public int depth() {
        return depth(root);
    }
    
    public int depth(Node node) {
        if (node == null) {
            return 0;
        } else {
            return 1 + Math.max(depth(node.left), depth(node.right));
        }
    }
    
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }
}

|  Modified class BinaryTree
|    Update overwrote class BinaryTree

BinaryTree btree = new BinaryTree();

|  Modified variable btree of type BinaryTree with initial value BinaryTree@f5f2bb7

for (int i=0; i < 1000; i++) {
    btree.add(new Node(i));
}

BinaryTree btree = new BinaryTree();
for (int i=0; i < 1000000; i++) {
    btree.add(new Node(Math.random()));
}

|  Modified variable btree of type BinaryTree with initial value BinaryTree@445b84c0

btree.depth()

|  Expression value is: 50
|    assigned to temporary variable $55 of type int

50

Non-recursive version of add

class Node {
    double data;
    Node left;
    Node right;
    
    Node(double data) {
        this.data = data;
    }    
}

class BinaryTree {
    Node root;
    
    public int depth() {
        return depth(root);
    }
    
    public int depth(Node node) {
        if (node == null) {
            return 0;
        } else {
            return 1 + Math.max(depth(node.left), depth(node.right));
        }
    }
    
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            Node current = root;
            while (true) {
                /// What goes here?
            }
        }
    }
}