## Jupyter at Bryn Mawr College

Public notebooks: /services/public/dblank / CS206 Data Structures / 2017-Spring / Notebooks

# 1. Family Tree¶

The Family Tree is also a recursive data structure.

In [14]:
%%file FamilyTree.java

class FamilyTree {
String name;
FamilyTree mother;
FamilyTree father;

FamilyTree(String name) {
this.name = name;
}

public static void main(String[] args) {
FamilyTree me = new FamilyTree("Doug");
me.mother = new FamilyTree("Norma");
me.father = new FamilyTree("Scotty");

System.out.println("Me: " + me.name);
System.out.println("Father: " + me.father.name);
System.out.println("Mother: " + me.mother.name);
}

}

Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/FamilyTree.java'.

In [15]:
! javac FamilyTree.java

In [16]:
! java FamilyTree

Me: Doug
Father: Scotty
Mother: Norma


## 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 list.

In [18]:
%%file Node.java

class Node<T> {
T data;
Node<T> left;
Node<T> right;

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

Created file '/home/dblank/public_html/CS206 Data Structures/2017-Spring/Notebooks/Node.java'.

In [19]:
! javac Node.java

class BinaryTree {
Node root;

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;

if (root == null) {
root = node;
} else {
}
}
}


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

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

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

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

In [6]:
import java.lang.Math;

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

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

if (left == null)
left = node;
else if (right == null)
right = node;
else {
if (Math.random() < .5) {
} else {
}

}

}

}




In [7]:
class BinaryTree {
Node root;

if (root == null) {
root = node;
} else {
}
}
}

|  Added class BinaryTree


In [8]:
BinaryTree btree = new BinaryTree();

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


In [9]:
btree.add(new Node(23));


In [10]:
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:

In [11]:
class BinaryTree {
Node root;

if (root == null) {
root = node;
} else {
}
}

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


In [12]:
BinaryTree btree = new BinaryTree();

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


In [13]:
btree.depth()

|  Expression value is: 0
|    assigned to temporary variable $15 of type int  Out[13]: 0 In [14]: btree.add(new Node(23));  In [15]: btree.depth()  | Expression value is: 1 | assigned to temporary variable$17 of type int


Out[15]:
1
In [16]:
btree.add(new Node(46));


In [17]:
btree.depth()

|  Expression value is: 2
|    assigned to temporary variable $19 of type int  Out[17]: 2 In [18]: btree.add(new Node(47)); btree.depth()  | Expression value is: 2 | assigned to temporary variable$21 of type int


Out[18]:
2
In [19]:
btree.add(new Node(47));
btree.depth()

|  Expression value is: 3
|    assigned to temporary variable $23 of type int  Out[19]: 3 In [23]: BinaryTree btree = new BinaryTree();  | Modified variable btree of type BinaryTree with initial value BinaryTree@5f150435  In [24]: for (int i=0; i < 1000000; i++) { btree.add(new Node(i)); }  What do you think the depth is? btree.depth();  In [25]: btree.depth();  | Expression value is: 23 | assigned to temporary variable$29 of type int


Out[25]:
23

# Lab 3: Sorted Binary Tree¶

In [26]:
class Node {
double data;
Node left;
Node right;

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

if (node.data < this.data) {
if (this.left == null) {
this.left = node;
} else {
}
} else {
if (this.right == null) {
this.right = node;
} else {
}
}
}
}

|  Modified class Node
|    Update overwrote class Node


In [27]:
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));
}
}

if (root == null) {
root = node;
} else {
}
}
}

|  Modified class BinaryTree
|    Update overwrote class BinaryTree


In [31]:
BinaryTree btree = new BinaryTree();

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


In [29]:
for (int i=0; i < 1000; i++) {
}


In [44]:
BinaryTree btree = new BinaryTree();
for (int i=0; i < 1000000; i++) {
}

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


In [45]:
btree.depth()

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


Out[45]:
50

In [ ]:
class Node {
double data;
Node left;
Node right;

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

In [ ]:
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));
}
}