Transcript 18-BinaryTrees

Chapter 18
Binary Trees
Data Structures and Design in Java
© Rick Mercer
18-1
A 3rd way to structure data
 We have considered two data structures for
implementing collection classes
—
—
Arrays
Singly-linked
 Both are linear
—
each element has one successor and one predecessor
(except the first and last)
 We now consider a hierarchical data structure
where each node may have two successors, each of
which which may have two successors
18-2
Trees in General
 A tree has a set of nodes and edges that connect them
 One node is distinguished as the root node
 Every node (except the root) is connected by exactly
one edge from exactly one other node
 A unique path traverses from the root to each node
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
A few more uses we will not be implementing
 Data base system implementation
 Document Object Model (DOM) implementation
—
Trees store html elements as objects, allowing many
languages to get, change, add, or delete html elements
 Compilers
—
Symbol Trees, Abstract Syntax Trees
 Seen as a CS logo
18-5
The Binary Tree we will be implementing
 Each node will store
—
—
—
a reference to a “left” node
a reference to an element type String here
and a reference to a “right” node
nodes
root
"T"
"L"
"R"
edges
root: an external reference like first we use in linked data
18-6
structures
Some tree terminology
Node
Path
Root
Parent
Child
Size
Leaves
Height
Levels
An element in the tree
The nodes visited as you travel from the root down
The node at the top It is upside down
The node directly above another node except root
A node below a given node left or right matters
Number of descendants plus one for the node itself
Nodes with zero children
The length of a path (# edges) height is -1 for empty trees
The top level is 0, increases by 1
18-7
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-8
Huffman Tree we will be implementing later
 Binary trees were used in a famous first file
compression algorithm
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'
0001101100100010000001000111111
—
31 bits vs. 12*8 = 96 bits
'h'
'r'
18-9
Binary Search Trees we will be implementing later
 Insert, search, remove? O(log n)
root
50
25
12
75
35
28
66
41
54
90
81
95
18-10
Expression Trees we will begin today
 Binary trees represent expressions at runtime
+
3
1
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
*
7
2
18-11
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-12
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-13
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-14
Traversing Trees
 We will use recursive backtracking 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-15
Implementing a Binary Tree
 We'll use an inner class again to store nodes TreeNode
 Need a reference to the element
 Need 2 references to the two children of a binary treee
—
—
the left and right subtrees, both of type?
could be null to indicate an empty tree
root = new TreeNode("*");
root
"*"
18-16
Add 2 More Binary Trees
root.left = new TreeNode("2");
root.right = new TreeNode("5");
root
"*"
"2"
"5"
18-17
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-18
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-19
Code Demo: Hard code a tree, traverse inorder
public class ExpressionTree {
private class TreeNode {
private TreeNode left;
private String data;
private TreeNode right;
public TreeNode(String theData) {
data = theData;
left = null;
right = null;
}
public TreeNode(TreeNode leftSubTree,
String theData,
TreeNode rightSubTree) {
left = leftSubTree;
data = theData;
right = rightSubTree;
}
} // end inner class TreeNode
private TreeNode root;
public ExpressionTree() { // TBA
18-20