Transcript 18-BinaryTreesx

Chapter 18
Binary Trees
Data Structures and Design in Java
© Rick Mercer
18-1
A 3rd major way to structure data
 We have considered two data structures for
implementing collection classes
—
—
Contiguous arrays
Singly- and Doubly-Linked structures
 Both are linear
—
each element has one successor and one
predecessor
 Now consider a hierarchical data structure
—
each node may have two or more successors,
each of which which may have two or more
successors
18-2
HTML pages sent to you as a tree
 Document Object Model (DOM) implementation
—
—
—
HTML elements sent as a standard DOM tree
Allows many browsers to render the HTML elements
We can get, change, add, or delete HTML elements
18-3
Trees are used in many ways
 Hierarchical file systems
—
—
In Windows, \ represents an edge or / in Unix
Each directory may be empty, have children, some of
which may be other directories
/
.Spotlight-V100
test
bin
sleep
etc
...
sync
...
nanorc
...
mail.rc
...
18-4
package dir;
import java.io.File;
public class Dir {
public static void main(String[] args) {
showAllFrom("/Users/mercer/Documents/Eclipseworkspaces" +
"/227Workspace/ExpressionTree");
}
private static void showAllFrom(String path) {
File folder = new File(path);
File[] listOfFiles = folder.listFiles();
if (listOfFiles == null)
return;
for (int i = 0; i < listOfFiles.length; i++) {
if (!listOfFiles[i].isHidden() && listOfFiles[i].isFile()) {
System.out.println(" " + listOfFiles[i].getName());
} else if (listOfFiles[i].isDirectory()) {
System.out.println(listOfFiles[i].getName() + ":");
showAllFrom(listOfFiles[i].getPath());
}
}
}
18-5
}
Mac Finder:
Dir.java output:
.settings:
org.eclipse.jdt.core.prefs
0.txt
1.txt
5.txt
7.txt
bin:
dir:
Dir.class
done:
ExpressionTree$TreeNode.class
ExpressionTree.class
ExpressionTreeTest.class
start:
ExpressionTree$TreeNode.class
ExpressionTree.class
ExpressionTreeTest.class
et7
src:
dir:
Dir.java
done:
ExpressionTree.java
ExpressionTreeTest.java
start:
ExpressionTree.java
ExpressionTreeTest.java
18-6
Huffman Tree we will be implementing later
 Binary trees were used in a famous first file
compression algorithm

David Huffman 1952
root
 Each character is stored in a leaf
 Follow the paths
—
—
—
—
0 go left, 1 go right
a is 01, e is 11
What is t?
't'
What is…
'a'
' '
'e'
0100011100100010111001000111111
—
—
'r'
31 bits vs. 12*8 = 96 bits 'h'
Used JPEG, MP3, HD TV compression
18-7
Some Tree Data Structure Uses
 Cell phone T9, type j
 Java’s TreeSet implementation
 Compilers
—
Symbol Tree, Abstract Syntax Tree
 Data base implementation
IBM’s IMS for example
 A tree used to be our Arizona CS logo
—
18-8
Terminology
node an object containing a data reference and left & right trees
root an external reference to the root node (or null if empty)
leaf a node that has no children
branch any internal node; neither the root node nor a leaf
parent a node that refers to this one
root
child a node that this node refers to
height = 3
level 1
sibling a node with a common parent
1
subtree the smaller tree of nodes on either
the left or right of the current node
level 2
2
3
height length of the longest path from the
root to any node (empty tree -1)
level 3 4
5
6
7
level or depth: length of the path
from a root to a given node
18-9
The Binary Tree we will be implementing
 Each TreeNode will store
—
—
—
a reference to a “left” TreeNode
a reference to the element (in this case, Strings)
and a reference to a “right” TreeNode
nodes
root
"T"
"L"
"R"
edges
root: an external reference like first we use in linked
18-10
data structures
Binary Trees
 A binary tree is a tree where all nodes have
zero, one, or two children
 Each node is a leaf (no children), has a right
child, has a left child, or both a left and right
child
root
1
2
3
4
5
6
18-11
Recursive Definition
• A binary tree is either:
– empty (null), or
– a root node that contains:
• data, a left tree, and a right tree
root
root
root
root
root
1
1
1
1
2
3
3
7
18-12
Expression Trees we will begin today
 Compilers build binary trees to represent
expressions at runtime (no parens)
+
3
1
*
7
With the infix expression
((3+(7*2))-1)
• Each parenthesized expression is
represented by a tree
• Each operand is a leaf
• each operator is an internal node
2
18-13
Evaluating Expression Trees
 To evaluate the expression tree:
—
Apply the parent's operator to its left and right subtrees
+
1
14
*
3
7
2
18-14
Evaluating Expression Trees
 To evaluate the expression tree:
—
Apply the parent's operator to its left and right subtrees
-
17
+
3
1
*
7
2
18-15
Evaluating Expression Trees
 To evaluate the expression tree:
—
Apply the parent's operator to its left and right subtrees
16
+
3
1
*
7
2
18-16
Traversing Trees
 Recursive backtracking allow us to “visit” nodes
+
3
1
Preview three tree traversals
• Inorder
3 + 7 * 2 - 1
• PostOrder 3 7 2 * + 1 • Preorder - + 3 * 7 2 1
*
7
2
18-17
Implementing a Binary Tree
 Use an inner class again to store nodes TreeNode
 Need a reference to the element
 Need 2 references to the 2 children: left and righte
—
—
the left and right subtrees, both of type TreeNode
could be null to indicate an empty tree
root = new TreeNode("*");
root
"*"
18-18
Add 2 More Binary Trees
root.left = new TreeNode("2");
root.right = new TreeNode("5");
root
"*"
"2"
"5"
18-19
Code Demo: Hard code a tree
public class ExpressionTree {
private class TreeNode {
private String data;
private TreeNode left;
private TreeNode right;
public TreeNode(String theData) {
data = theData;
left = null;
right = null;
}
public TreeNode(TreeNode lefTree, String theData, TreeNode righTree) {
left = lefTree;
data = theData;
right = righTree;
private void hardCodeThisTree() {
}
//
root -> *
} // end class TreeNode
//
//
//
//
// The external reference starting point
private TreeNode root;
public ExpressionTree() {
root = null;
}
}
/ \
+
3
/ \
5
4
}
18-20
Tree Traversals
 Tracing the elements in a tree
—
—
—
Can’t go from first to last
Need to go up and down the levels
Recursion helps keep track with
backtracking
18-21
InOrder Tree Traversal
 Visit the left binary tree of each root before
visiting the root, then visit the right
inOrder(root)
+
inOrder (TreeNode t)
if the tree is not empty
inOrderTraverse(left Child)
visit the root
inOrderTraverse(right Child)
3
1
*
7
2
18-22