Slide #1.

Binary Trees Wellesley College CS230 Lecture 17 Thursday, April 5 Handout #28 PS4 due 1:30pm Tuesday, April 10 17 - 1
More slides like this


Slide #2.

Motivation: Inefficiency of Linear Structures Up to this point our focus has been linear structures: arrays, vectors, linked lists Some operations on linear structures are cheap: • Constant time: Get/set elt at a given index in array/vector Add elt to the end of a vector Add elt to the front of a im/mutable list Add elt to the back of a mutable list (if have pointer to last node) • Logarithmic time: Binary search on sorted array/vector Other operations are expensive (linear in size): Inserting/deleting elt at arbitrary position in an array/vector/list Finding an element in a list (even a sorted one) There is no linear structure for which insertion, deletion, and membership operations (e.g. in priority queues, sets, bags, and tables) are all cheaper than linear. 17 - 2
More slides like this


Slide #3.

Idea: Branching of Binary Search + Linking of Linked Lists → Binary Trees A binary tree is either • a leaf: • a node with (1) a left subtree (2) a value and (3) a right subtree: binary tree node left subtree value right subtree 17 - 3
More slides like this


Slide #4.

A Sample Binary Tree F A F C D B A G E Values are often shown in the nodes C D B G E Often, the leaves are not shown, but they’re still there! 17 - 4
More slides like this


Slide #5.

Tree Terminology Nodes A and C are the children of node F; F is the parent of A and C; A and C are siblings. Grandparents, grandchildren, etc. defined similarly. A node without a parent is a root. E.g. node F D is the root of the tree, and node A is the root of F’s left subtree (considered separately from the whole tree). A descendant of a node n is a node on the path from n to a leaf. E.g. nodes D, B, and E are the descendants of A. An ancestor of a node n is a node on the path from n to the root. E.g. Nodes B, A, and F are the ancestors of E. F A C B G E 17 - 5
More slides like this


Slide #6.

More Tree Terminology The height of a node n is length of the longest path from n to a leaf below it. E.g., node G has height 1, node C has height 2, and node F has height 4. The depth of a node n is the length of the path from n to the root. E.g., node F has depth 0, D node C has depth 1, and node G has depth 2. A binary tree is height-balanced iff at every node n, the heights of n’s left and right subtrees differ by no more than 1. The example tree is height-balanced, but would not be if G were removed. (There are other notions of tree balance in CS231.) F A C B G E 17 - 6
More slides like this


Slide #7.

Binary Search Trees To get full advantage of binary trees for data structures, need the values to be ordered. A binary search tree (BST) is a binary tree in which the following properties hold at every node: (1) All elements in the left subtree are ≤ the value; (2) All elements in the right subtree are ≥ the value. Here is a sample BST →E BSTs will be very important in the next lecture, when we use binary trees to implement data structures like sets, bags, and tables For now, we’ll stick with generic binary trees. B F A D C G 17 - 7
More slides like this


Slide #8.

Trees: An Omnipresent Data Representation • • • • • • • • Family trees File system Sport tournaments Animal kingdom Organizational chart Java class hierarchy A graph without cycles A home’s plumbing and electrical systems • … • A convenient data structure A tree T is a set of one or more nodes s.t. T is partitioned into two disjoint subsets: • A single node r, the root • Sets that are also trees, called subtrees of r 17 - 8
More slides like this


Slide #9.

The Binary Tree 17 - 9
More slides like this


Slide #10.

Arithmetic Expressions as Trees a-b a-(b/c) a (a-b)*c b * a / b c a c b Arithmetic expressions are often represented as binary trees. Internal nodes are operations - Leaves are numbers/variables. Operator precedence is enforced by the tree shape. 17 - 10
More slides like this


Slide #11.

TreeInterface public interface TreeInterface { public boolean isLeaf (); public Object getValue (); public Tree getLeft (); public Tree getRight (); public void setValue (Object newValue); public void setLeft (Tree newLeft); public void setRight (Tree newRight); public String toString (); } 17 - 11
More slides like this


Slide #12.

Example public static void main(String[] args) { Tree T = new Tree(); T = new Tree("A", new Tree(), new Tree()); Tree tl = new Tree("B", new Tree(), new Tree()); Tree tr = new Tree("C", new Tree(), new Tree()); T.setLeft(tl); T.setRight(tr); T.getLeft().setValue(new Integer(5)); T.setRight(T.getRight().getRight() ); • Draw T’s contents . (. A .) ((. B .) A (. C .)) ((. 5 .) A (. C .)) ((. 5 .) A .) } 17 - 12
More slides like this


Slide #13.

Tree Implementation Contract public Tree () public Tree (Object val, Tree lt, Tree rt) private Object value; private Tree lt, rt; private boolean isLeaf; lt value isLeaf rt public boolean isLeaf () public Object getValue () public Tree getLeft () public Tree getRight () public void setValue (Object newValue) “Jane” F public void setLeft (Tree newLeft) public void setRight (Tree newRight) “Sally” F “Joe” F public String toString () / “” T / / “” T / / “” T / / “” T 17 - 13/
More slides like this


Slide #14.

public class Tree implements TreeInterface { // instance variables private Object value; private Tree left, right; private boolean isLeaf; // constructors public Tree () { isLeaf = true; } public Tree (Object value, Tree lt, Tree rt) { this.value = value; this.left = lt; this.right = rt; isLeaf = false; } // instance methods public boolean isLeaf () { // returns true if the tree is a leaf (i.e. empty tree) return isLeaf; } public Object getValue () { if (isLeaf) throw new RuntimeException ("Attempt to get value of empty tree"); else return value; } public Tree getLeft () { if (isLeaf) throw new RuntimeException ("Attempt to get left subtree of an empty tree"); else return left; } public Tree getRight () { if (isLeaf) throw new RuntimeException ("Attempt to get right subtree of an empty tree"); else return right; } 17 - 14
More slides like this


Slide #15.

And the Rest... public void setValue (Object newValue){ // sets the Object in the root node of the tree to a new value if (isLeaf) throw new RuntimeException ("Attempt to get value of empty tree"); else this.value = newValue; } public void setLeft (Tree newLeft) { // changes the left subtree to a new tree } public void setRight (Tree newRight){ // changes the right subtree to a new tree } 17 - 15
More slides like this


Slide #16.

How Do You Print a Tree? public String toString () { // returns a String representation of the contents of a Tree * / 10 - + 3 5 2 } 17 - 16
More slides like this


Slide #17.

Ways to Visit the Nodes of a Tree public String toString () { // returns a String representation of the contents of a Tree if (this.isLeaf()) return ""; else return "(" + this.getLeft().toString() + " " + this.getValue() + " " + this.getRight().toString() + ")"; } * / 10 - + 3 5 2 17 - 17
More slides like this


Slide #18.

Syntatic Sugar - a bunch of static’s public static Tree leaf () { return new Tree(); } public static Tree node (Object val, Tree lt, Tree rt) { return new Tree(val, lt, rt); } public static boolean isLeaf (Tree t) { return t.isLeaf; } public static Object getValue(Tree t) { return t.getValue(); } public static Tree getLeft(Tree t) { return t.getLeft(); } public static Tree getRight(Tree t){ return t.getRight(); } public static void setValue (Tree t, Object newValue) { t.setValue(newValue); } public static void setLeft (Tree t, Tree newLeft) { t.setLeft(newLeft); } public static void setRight (Tree t, Tree newRight) { t.setRight(newRight); } // using the new notation: Tree T = leaf(); T = node("A", leaf(), leaf()); Tree tl = node("B", leaf(), leaf()); Tree tr = node("C", leaf(), leaf()); setLeft(T, tl); setRight(T, tr); setValue(getLeft(T),new Integer(5)); setRight(T, getRight(getRight(T)) ); 17 - 18
More slides like this


Slide #19.

Traversal of a Binary Tree • Is a way of visiting each node in the tree • Recursive traversal algorithms – Preorder traversal – Inorder traversal – Postorder traversal 1 2 3 7 4 5 6 2 1 6 7 4 3 7 5 1 5 6 4 2 3 17 - 19
More slides like this


Slide #20.

Three Ways to Traverse the Tree public static void preOrderWrite (Tree t) // prints contents of the tree t using if (!isLeaf(t)) { System.out.print(" " + getValue(t)); preOrderWrite(getLeft(t)); preOrderWrite(getRight(t)); } } public static void inOrderWrite (Tree t) { // prints contents of the tree t using if (!isLeaf(t)) { inOrderWrite(getLeft(t)); System.out.print(" " + getValue(t)); inOrderWrite(getRight(t)); } } public static void postOrderWrite (Tree t) // prints contents of the tree t using if (!isLeaf(t)) { postOrderWrite(getLeft(t)); postOrderWrite(getRight(t)); System.out.print(" " + getValue(t)); } } { preOrder traversal of the nodes inOrder traversal of the nodes { postOrder traversal of the nodes 17 - 20
More slides like this


Slide #21.

Tree Contract (interface + instance vars) public Tree () public Tree (Object val, Tree lt, Tree rt) private private private private lt value isLeaf rt Tree lt; Object value; boolean isLeaf; Tree rt; public boolean isLeaf () public Object getValue () public void setValue (Object newValue) public Tree getLeft () public void setLeft (Tree newLeft) public Tree getRight () public void setRight (Tree newRight) “Jane” F public String toString () “Sally” / “” T / / “” T / / “” F “Joe” T / / “” F T 17 - 21/
More slides like this


Slide #22.

Syntatic Sugar public static Tree leaf () { return new Tree(); } public static Tree node (Object val, Tree lt, Tree rt) { return new Tree(val, lt, rt); } public static boolean isLeaf (Tree t) { return t.isLeaf; } public static Object getValue(Tree t) { return t.getValue(); } public static Tree getLeft(Tree t) { return t.getLeft(); } public static Tree getRight(Tree t){ return t.getRight(); } public static void setValue (Tree t, Object newValue) { t.setValue(newValue); } public static void setLeft (Tree t, Tree newLeft) { t.setLeft(newLeft); } public static void setRight (Tree t, Tree newRight) { t.setRight(newRight); } Tree T = leaf(); T = node("A", leaf(), leaf()); Tree tl = node("B", leaf(), leaf()); Tree tr = node("C", leaf(), leaf()); setLeft(T, tl); setRight(T, tr); setValue(getLeft(T),new Integer(5)); setRight(T, getRight(getRight(T)) );17 - 22
More slides like this


Slide #23.

Basic Operations: height() • Height of a node n is the distance from the node to its furthest child public static int height (Tree t){ // returns the height of the tree t if (isLeaf(t)) return 0; else return 1 + Math.max( height(getLeft(t)), height(getRight(t))); } 17 - 23
More slides like this


Slide #24.

Basic Operations: countNodes() public static int countNodes (Tree t) { // returns the number of nodes in tree t if ( ) else } 17 - 24
More slides like this


Slide #25.

Basic Operations: countOccurrences() • Count occurrences of S in tree T – If root contains S, it is 1 + – The number of times it occurs in the left subtree + – The number of times it occurs in the right subtree public static int countOccurrences (Tree t, String S) { // returns the number of nodes in the tree t that contain // the input String S if (isLeaf(t)) return 0; F else { if (((String)getValue(t)).equals(S)) return 1 + countOccurrences(getLeft(t), S) + A B countOccurrences(getRight(t), S); else return countOccurrences(getLeft(t), S) + countOccurrences(getRight(t), S); D A } A A C } 17 - 25
More slides like this


Slide #26.

Basic Operations: isMember() isMember() returns true iff the input word is contained somewhere in the tree public static boolean isMember (String word, Tree t) { if (isLeaf(t)) return false; else if (((String)t.getValue()).equals(word)) return true; else return(isMember(word, getLeft(t)) || isMember(word,getRight(t))); } 17 - 26
More slides like this


Slide #27.

Full and Complete • Full binary tree is a binary tree of height h with no missing nodes – All leaves are at level h – All internal nodes each have two children • Complete binary tree is a binary tree of height h that is full to level h – 1 and has level h filled in from left to right • Full binary => complete • There is a simpler implementation for full and complete trees 0 Helen 1 Wendy Nina 2 Caitlin 3 Joan 4 5 Merideth 6 7 8 Helen Wendy Caitlin Joan Nina Merideth 17 - 27
More slides like this


Slide #28.

Recursive Definition of Full Binary Tree • Full binary tree – If T is empty, T is a full binary tree of height 0 – Else if T is not empty T is a full binary tree if its root’s subtrees are both full binary trees of height h – 1 public static boolean isFullBT (Tree t) { if else } 17 - 28
More slides like this


Slide #29.

Array Representation of Binary Trees A binary tree can be represented using an array of tree nodes tree item lt rt Each tree node contains a data portion and two indexes (one for each of the node’s children) Requires the creation of a free list which keeps track of available nodes The free list is being kept inside the tree array! Allows for representation of any kind of tree, not just complete ones Helen Wendy Caitlin 0 Helen 1 2 1 Wendy 3 4 2 Nina 5 -1 3 Caitlin -1 -1 4 Joan -1 -1 5 Merideth -1 -1 6 -1 7 7 -1 8 8 -1 9 … … 0 6 root free …… Nina Joan Merideth 17 - 29
More slides like this


Slide #30.

Basic Operations: isBalanced() A binary tree is balanced iff the height of any node’s right subtree differs by no more than 1 from the height of the node’s left subtree • Complete binary trees are balanced public static boolean isBalanced(Tree t) { if (isLeaf(t)) return true; else return ((Math.abs(height(getLeft(t)) - height(getRight(t))) <= 1) && (isBalanced(getLeft(t))) && (isBalanced(getRight(t)))); } 17 - 30
More slides like this


Slide #31.

Recording the Shape of a Tree public static Tree makeStarTree (Tree t) { // returns a new tree that has // the same size and shape as t, but with // all nodes in the tree containing // a String with a * character if (isLeaf(t)) return leaf(); else return node ("*", makeStarTree(getLeft(t)), makeStarTree(getRight(t))); } alex joe bo claire al harry jane * * * * * * * 17 - 31
More slides like this


Slide #32.

Applying a Function on a Tree public static Tree makeReverseTree (Tree t) { // returns a new tree that is the same size // and shape as t, but with all of the // Strings labels in the tree reversed if (isLeaf(t)) return leaf(); else return node (reverseString((String)getValue(t)), makeReverseTree(getLeft(t)), makeReverseTree(getRight(t))); } public static String reverseString (String S) { // returns a String that is the reverse of the input String S String newS = ""; for (int i = 0; i < S.length(); i++) newS = S.charAt(i) + newS; return newS; } alex joe bo claire al harry jane xela eoj erialc la enaj ob yrrah 17 - 32
More slides like this


Slide #33.

Destructive Versions public static void makeStarTree2 (Tree t) { // alters the contents of the input tree so that all of the // nodes contain a String with a star character if (!(isLeaf(t))) { setValue(t, "*"); makeStarTree2(getLeft(t)); makeStarTree2(getRight(t)); } } public static void makeReverseTree2 (Tree t) { // alters the contents of the input tree so that all of the // Strings in the tree are reversed if (!(isLeaf(t))) { setValue(t, reverseString((String)getValue(t))); makeReverseTree2(getLeft(t)); makeReverseTree2(getRight(t)); } } 17 - 33
More slides like this


Slide #34.

The daVinci Tree ;-) alex public static void flipTree (Tree t) { // alters the shape of tree // by changing it a mirror reversal if (!isLeaf(t)) { Tree tempTree = getLeft(t); setLeft(t, getRight(t)); setRight(t, tempTree); flipTree(getLeft(t)); flipTree(getRight(t)); } } joe bo claire al harry jane alex bo harry joe al claire jane 17 - 34
More slides like this


Slide #35.

The Index of an Array Representation public static Tree makeLabelTree (Tree t) { // returns a new tree with the same shape // and size as the input tree, // in which the value in each node // of the new tree is the index // of the node in an array representation return labelTree(t, 1); } alex bo joe al claire harry public static Tree labelTree (Tree t, int label) { // recursive helper method of makeLabelTree() if (isLeaf(t)) 2 return leaf(); else return node(new Integer(label), 4 labelTree(getLeft(t), 2*label), labelTree(getRight(t), 2*label+1)); } jane 1 3 6 7 13 17 - 35
More slides like this


Slide #36.

makeHeightTree() alex public static Tree makeHeightTree (Tree t) { /* returns a new tree that has the same size and shape as t, and in which the node value is the height of the tree rooted at the corresponding node of the input tree */ if (isLeaf(t)) return leaf(); else return node(new Integer(height(t)), makeHeightTree(getLeft(t)), makeHeightTree(getRight(t))); } bo joe al claire harry jane 4 2 1 3 2 1 1 17 - 36
More slides like this


Slide #37.

makeLevelTree() public static Tree makeLevelTree (Tree t) { /* returns a new tree that is the same size and shape as t, in which the value in each node of the new tree is the level of the corresponding node in the input tree */ return levelTree(t, 0); } public static Tree levelTree (Tree t, int h) { // recursive helper method for makeLevelTree() if (isLeaf(t)) return leaf(); else return node(new Integer(h + 1), levelTree(getLeft(t), h + 1), levelTree(getRight(t), h + 1)); } alex bo joe al claire harry jane 1 2 3 2 3 3 4 17 - 37
More slides like this


Slide #38.

Binary Search Tree (BST) • A binary tree that for each node n: – n’s value is greater than all values in its left subtree T L – n’s value is less than all values in its right subtree T R – Both TL and TR are binary search trees 5 Helen 2 6 Elaine 1 4 Nina 7 Caitlin Gina Merideth Wendy 3 A binary search tree of numbers A binary search tree of names 17 - 38
More slides like this


Slide #39.

Decision Trees for Expert Systems • • • • • • • • • • • • • • • • • • • • Welcome to the game of Twenty Questions! Think of an animal and I will try to guess it Does it have four legs? yes Does it have hooves? no Is it a dog? yes I won! Keep playing? yes Think of another animal and I will try to guess it Does it have four legs? no Does it swim? no Is it an ostrich? no I give up! What is your animal me! Does it have 4 legs? no yes Does it swim? no Is it an Ostrich? yes Is it a Goldfish? Does it have hooves? no Is it a Dog? yes Is it a Cow? 17 - 39
More slides like this