Transcript Java Review - Computer Science Department | California

Chapter 7: Trees
Objectives:
Introduce general tree structure and
Tree ADT
Discuss the depth and height of trees
Introduce the tree traversal algorithms
Specialize to binary trees
Implement binary trees with linked
structure and array-list structure
Introduce the Template Method Pattern
CSC311: Data Structures
1
What is a Tree
In computer science, a
tree is an abstract
model of a hierarchical
structure
A tree consists of nodes
with a parent-child
relation
Applications:
– Organization charts
– File systems
– Programming
environments
Trees
Computers”R”Us
Sales
US
Europe
Manufacturing
International
Asia
CSC311: Data Structures
Laptops
R&D
Desktops
Canada
2
Tree Terminology
Root: node without parent (A)
Internal node: node with at
least one child (A, B, C, F)
External node (a.k.a. leaf ):
node without children (E, I, J,
K, G, H, D)
Ancestors of a node: parent,
grandparent, grandgrandparent, etc.
Depth of a node: number of
ancestors
Height of a tree: maximum
depth of any node (3)
Descendant of a node: child,
grandchild, grand-grandchild,
etc.
Trees
Subtree: tree
consisting of a node
and its descendants
A
B
E
C
F
I
CSC311: Data Structures
J
G
K
D
H
subtree
3
Tree ADT
We use positions to
abstract nodes
Generic methods:
–
–
–
–
integer size()
boolean isEmpty()
Iterator iterator()
Iterator positions()
Accessor methods:
– position root()
– position parent(p)
– positionIterator
children(p)
Trees
Query methods:
– boolean isInternal(p)
– boolean isExternal(p)
– boolean isRoot(p)
Update method:
– object replace (p, o)
Additional update
methods may be defined
by data structures
implementing the Tree
ADT
CSC311: Data Structures
4
Depth of a Node
The depth of a
node v in a tree T
is defined as:
Algorithm depth(T, v)
Input: Tree T and a node v
Output: an integer that is the
depth of v in T
– If v is the root,
then its depth is 0; If v is the root of T then
return 0
– Otherwise, its
Else
depth is one plus
return 1 + depth(T, parent(v))
the depth of its
parent
Trees
CSC311: Data Structures
5
Height of a Node
The height of a
node v in a tree T
is defined as:
Algorithm height(T, v)
Input: Tree T and a node v
Output: an integer that is the
height of v in T
– If v is an external,
then its height is 0; If v is an external of T then
return 0
– Otherwise, its
Else
height is one plus
h0
the maximum
for each child w of v in T do
height of its
hmax(h, height(T,w))
children
return 1+h
Trees
CSC311: Data Structures
6
Features on Height
1. The height of a nonempty tree T is
equal to the maximum depth of an
external node of T
2. Let T be a tree with n nodes, and
let cv denote the number if children
of a node v of T. The summing over
the vertices in T, vcv=n-1.
Trees
CSC311: Data Structures
7
Preorder Traversal
A traversal visits the nodes
Algorithm preOrder(v)
of a tree in a systematic
visit(v)
manner
for each child w of v
In a preorder traversal, a
node is visited before its
preorder (w)
descendants
Application: print a 1
structured document Make Money Fast!
2
5
1. Motivations
Trees
9
2. Methods
3
4
1.1 Greed
1.2 Avidity
6
2.1 Stock
Fraud
CSC311: Data Structures
7
2.2 Ponzi
Scheme
References
8
2.3 Bank
Robbery
8
Postorder Traversal
In a postorder traversal, a
node is visited after its
descendants
Application: compute
space used by files in a
directory and its
subdirectories
9
Algorithm postOrder(v)
for each child w of v
postOrder (w)
visit(v)
cs16/
3
7
homeworks/
Trees
8
todo.txt
1K
programs/
1
2
h1c.doc
3K
h1nc.doc
2K
4
DDR.java
10K
CSC311: Data Structures
5
Stocks.java
25K
6
Robot.java
20K
9
Binary Trees
Applications:
A binary tree is a tree with the
following properties:
– arithmetic
expressions
– decision processes
– searching
– Each internal node has at most
two children (exactly two for
proper binary trees)
– The children of a node are an
ordered pair
A
We call the children of an
internal node left child and right
child
Alternative recursive definition:
a binary tree is either
– a tree consisting of a single
node, or
– a tree whose root has an
ordered pair of children, each of
which is a binary tree
Trees
CSC311: Data Structures
B
C
D
E
H
F
G
I
10
Arithmetic Expression Tree
Binary tree associated with an arithmetic
expression
– internal nodes: operators
– external nodes: operands
Example: arithmetic expression tree for the
expression (2  (a - 1) + (3  b))
+


-
2
a
Trees
3
b
1
CSC311: Data Structures
11
Decision Tree
Binary tree associated with a decision process
– internal nodes: questions with yes/no answer
– external nodes: decisions
Example: dining decision
Want a fast meal?
No
Yes
How about coffee?
Trees
On expense account?
Yes
No
Yes
No
Starbucks
Spike’s
Al Forno
Café Paragon
CSC311: Data Structures
12
BinaryTree ADT
The BinaryTree ADT
extends the Tree
ADT, i.e., it inherits
all the methods of
the Tree ADT
Additional methods:
–
–
–
–
Trees
position
position
boolean
boolean
Update methods
may be defined
by data structures
implementing the
BinaryTree ADT
left(p)
right(p)
hasLeft(p)
hasRight(p)
CSC311: Data Structures
13
Properties of Proper Binary Trees
Properties:
– e=i+1
– n = 2e - 1
– hi
– h  (n - 1)/2
– e  2h
– h  log2 e
– h  log2 (n + 1) - 1
Notation
n number of
nodes
e number of
external nodes
i number of
internal nodes
h height
Trees
CSC311: Data Structures
14
Inorder Traversal
In an inorder traversal a
node is visited after its
left subtree and before its
right subtree
Application: draw a binary
tree
Algorithm inOrder(v)
if hasLeft (v)
inOrder (left (v))
visit(v)
if hasRight (v)
inOrder (right (v))
– x(v) = inorder rank of v
– y(v) = depth of v
6
2
8
1
4
3
Trees
7
9
5
CSC311: Data Structures
15
Print Arithmetic Expressions
Specialization of an
inorder traversal
– print operand or operator
when visiting node
– print “(“ before traversing
left subtree
– print “)“ after traversing
right subtree
+


-
2
a
Trees
3
1
b
Algorithm printExpression(v)
if hasLeft (v)
print(“(’’)
inOrder (left(v))
print(v.element ())
if hasRight (v)
inOrder (right(v))
print (“)’’)
((2  (a - 1)) + (3  b))
CSC311: Data Structures
16
Evaluate Arithmetic
Expressions
Specialization of a
postorder traversal
– recursive method
returning the value of a
subtree
– when visiting an
internal node, combine
the values of the
subtrees
+


-
2
5
Trees
Algorithm evalExpr(v)
if isExternal (v)
return v.element ()
else
x  evalExpr(leftChild (v))
y  evalExpr(rightChild (v))
  operator stored at v
return x  y
3
2
1
CSC311: Data Structures
17
Euler Tour Traversal
Generic traversal of a binary tree
Includes a special cases the preorder, postorder and inorder
traversals
Walk around the tree and visit each node three times:
– on the left (preorder)
– from below (inorder)
– on the right (postorder)
+
L
2


R
B
5
Trees
3
2
1
CSC311: Data Structures
18
Template Method Pattern
Generic algorithm that
can be specialized by
redefining certain steps public abstract class EulerTour {
protected BinaryTree tree;
Implemented by means
protected void visitExternal(Position p, Result r) { }
of an abstract Java class
protected void visitLeft(Position p, Result r) { }
Visit methods that can
protected void visitBelow(Position p, Result r) { }
be redefined by
protected void visitRight(Position p, Result r) { }
subclasses
protected Object eulerTour(Position p) {
Template method eulerTour
Result r = new Result();
– Recursively called on
the left and right
children
– A Result object with
fields leftResult, rightResult
and finalResult keeps track
of the output of the
recursive calls to eulerTour
Trees
if tree.isExternal(p) { visitExternal(p, r); }
else {
visitLeft(p, r);
r.leftResult = eulerTour(tree.left(p));
visitBelow(p, r);
r.rightResult = eulerTour(tree.right(p));
visitRight(p, r);
return r.finalResult;
}…
CSC311: Data Structures
19
Specializations of EulerTour
We show how to
specialize class
EulerTour to
evaluate an
arithmetic
expression
Assumptions
– External nodes
store Integer
objects
– Internal nodes
store Operator
objects supporting
method
operation (Integer, Integer)
Trees
public class EvaluateExpression
extends EulerTour {
protected void visitExternal(Position p, Result r) {
r.finalResult = (Integer) p.element();
}
protected void visitRight(Position p, Result r) {
Operator op = (Operator) p.element();
r.finalResult = op.operation(
(Integer) r.leftResult,
(Integer) r.rightResult
);
}
…
}
CSC311: Data Structures
20
Linked Structure for Trees
A node is represented by
an object storing
– Element
– Parent node
– Sequence of children
nodes

B

Node objects implement
the Position ADT

A
D
F
B

C
Trees
F
D
A
E
C
CSC311: Data Structures

E
21
Linked Structure for Binary Trees
A node is represented
by an object storing
–
–
–
–
Element
Parent node
Left child node
Right child node

Node objects
implement the Position
ADT
B

B
A
Trees
A
D
C

D

E
CSC311: Data Structures

C


E
22
Array-Based Representation
of Binary Trees
nodes are stored in an
array
1
A
…
2
3
B

let rank(node) be defined as follows:



Trees
D
4
rank(root) = 1
if node is the left child of parent(node),
rank(node) = 2*rank(parent(node))
if node is the right child of parent(node),
rank(node) = 2*rank(parent(node))+1
CSC311: Data Structures
5
E
6
7
C
F
10
J
11
G
H
23
Array-Based Representation of
Binary Trees: Properties
Let n be the number of nodes of a binary tree T
 Let pM be the maximum value of rank(v) over all the
nodes of T
 The array size N = pM+1
 In the worst case, N = 2n

Trees
CSC311: Data Structures
24