Transcript Lecture Notes for Recersion and Trees

Recursion
Recursion is a concept of defining a
method that makes a call to itself.
Trees
1
Recursion
return 15+A[4]=20
Algorithm LinearSum(A, n)
LinearSum(A,5)
Input: an integer array A of n elements
Output: The sum of the n elements
return 13+A[3]=15
LinearSum(A,4)
return 7+A[2]=13
if n=1 then return A[0] else
return LinearSum(A, n-1)+A[n-1]
• The recursive method should always
possess—the method terminates.
•We did it by setting :” if n=1 then
return A[0]”
A={4,3,6,2,5}
Trees
LinearSum(A,3)
LinearSum(A,2)
Return 4+A[1]=7
Return A[0]=4
LinearSum(A,1)
The compiler of any high level computer
language uses a stack to handle
recursive calls.
2
Factorial
Example:
f(n)=n!=n×(n-1)×(n-2)×…×2×1
and 0!=1.
It can also be written as f(n)=n×f(n-1) and f(0)=1.
Java code:
Public static int recursiveFactorial(int n) {
if (n==0) return 1;
else return n*recursiveFactorial(n-1);
}
Trees
3
Factorial
return f(4)=4*f(3)=24
Public static int recursiveFactorial(int n){
if (n==0) return 1;
else return n*recursiveFactorial(n-1);}
The recursive method should always
possess—the method terminates.
•We did it by setting :” if n=0 then
recursiveFactorial(4)
return f(3)=3*f(2)=6
recursiveFactorial(3)
return f(2)=2*f(1)=2
recursiveFActorial(2)
return 1”
recursiveFactorial(1)
return f(1)=1*1=1
Return f(0)=1
recursiveFactorial ( 0)
f(n)=n*f(n-1) for n>0 and f(0)=1.
Trees
4
ReverseArray
Algorithm ReverseArray(A, i, j):
input: An array A and nonnegative integer indices i and
j
output: The reversal of the elements in A starting at
index i and ending at j
if i<j then
{Swap A[i] and A[j]
ReverseArray(A, i+1, j-1)}
A={4,2,3,1}
return
ReverseArray{A, 0, 3)
A={1, 2, 3, 4}.
ReverseArray{A, 1 2)
Trees
A=(4,3,2,1}
5
Part-C
Trees
University
Fac. of
Sci. & Eng.
CS Dept.
EE Dept.
Bus. School
Law School
Math.
Dept.
Trees
6
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:
US

Organization charts
File systems

arithmetic expression

Computers”R”Us
Sales
Manufacturing
International
Europe
Asia
Laptops
R&D
Desktops
Canada
Remark: A tree is a special kind of
graph, where there is not circuit.
Trees
7
File System on Computers
H:
CS5302
net
readme
source
Node.java
CS5301
a.java
Others
b.java
Stack.java
Trees
8
Tree Terminology
Root: node without parent (e.g. A)
Internal node: node with at least
one child (e.g. A, B, C, F)
External node (or leaf ): node
without children (E, I, J, K, G, H, D)
Ancestors of a node: parent,
grandparent, grand-grandparent,
etc.
Depth of a node: number of
ancestors
E
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
C
F
I
J
G
K
D
H
subtree
9
Tree Terminology
Ordered tree: There is a
linear ordering defined
for the children of each
node.
Example: The order among
siblings are from left to
Ch1
right.
Ch1 Ch2 Ch3;
S.1.1
S.1.2
S1.1 S1.2;
S2.1 S2.1;
1.2.1 1.2.2
1.2.1 1.2.2 1.2.3;
Trees
Book
Ch2
S.2.1
Ch3
S.2.2
1.2.3
10
Tree ADT (§ 6.1.2)
A set of nodes with parentchild relationship.
Generic methods:


Query methods:


integer size()
boolean isEmpty()

Update method:
Accessor methods:




boolean isInternal(p)
boolean isExternal(p)
boolean isRoot(p)
root() returns the tree’s root.
parent(p) returns p’s parent
children(p) returns an iterator
of the children of node v.
Element() return the object
stored on this node.
Trees

object replace (p, o):
replace the content of node
p with o.
Additional update methods
may be defined by data
structures implementing the
Tree ADT
11
Binary Trees (§ 6.3)
Applications:
A binary tree is a tree with the
following properties:



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
arithmetic expressions
decision processes
searching
B
C
D
E
H
Trees
F
G
I
12
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
3
b
1
Trees
13
Decision Tree
Binary tree associated with a decision process


internal nodes: questions with yes/no answer
external nodes: decisions
Example: drinking decision
Want to drink ?
No
Yes
How about coffee?
Yes
Here it is
Bye-Bye
No
How about tee
No
Yes
Here it is
No
Here is your water
Trees
14
Inorder Traversal
(just for binary tree)
In an inorder traversal a
node is visited after its left
subtree and before its right
subtree
Algorithm inOrder(v)
if hasLeft (v)
inOrder (left (v))
visit(v)
if hasRight (v)
inOrder (right (v))
6
2
8
1
4
3
7
9
5
Trees
15
Inorder Traversal (Another
example)
6
.
8
4
5
2
1
7
10
3
9
11
The number on a node is bigger than the
numbers on its Right sub-tree and smaller
than7the numbers on it left sub-tree.
Trees
16
BinaryTree ADT (§ 6.3.1)
The BinaryTree ADT
extends the Tree
ADT, i.e., it inherits
all the methods of
the Tree ADT
Additional methods:




Update methods
may be defined by
data structures
implementing the
BinaryTree ADT
position left(p)
position right(p)
boolean hasLeft(p)
boolean hasRight(p)
Trees
17
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
3
Algorithm printExpression(v)
if hasLeft (v)
print(“(’’)
inOrder (left(v))
print(v.element ())
if hasRight (v)
inOrder (right(v))
print (“)’’)
b
((2  (a - 1)) + (3  b))
1
Trees
18
-
Print Arithmetic Expressions
+
10
+


-
2
x
a
3
b
1
((x+((2  (a - 1)) + (3  b)))-10)
Trees
19
Remarks:
They like this part the best because it is easy and contains more example. 5.41
Trees
20