COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 11-3 : Binary Trees
Giulia Alberini, Fall 2020 Slides adapted from Michael Langer’s
WHAT ARE WE GOING TO DO IN THIS VIDEO?
Binary Trees Expression Trees
BINARY TREES
BINARY TREES
Each node has at most 2 children!
BINARY TREES
Q: What is the maximum number of nodes 𝑛 in a binary tree of height h?
Height h (e.g. 3)
BINARY TREES
Q: What is the maximum number of nodes 𝑛 in a binary tree of height h?
Height h (e.g. 3)
A: 𝑛=1+2+4+⋯+2h =2h+1−1
BINARY TREES
Q: What is the minimum number of nodes 𝑛 in a binary tree of height h?
Height h (e.g. 3)
BINARY TREES
Q: What is the minimum number of nodes 𝑛 in a binary tree of height h?
Height h (e.g. 3)
A: 𝑛=h+1
BINARY TREES – IMPLEMENTATION
class BTree
BTNode
:
class BTNode
T element;
BTNode
BTNode
: }
}
BINARYTREETRAVERSAL (DEPTHFIRST)
Rooted Tree Binary Tree (last lecture)
depthFirst(root){
if (root is not empty){
visit root
for each child of root depthFirst( child )
} }
BINARYTREETRAVERSAL (DEPTHFIRST)
Rooted Tree Binary Tree (last lecture)
preorder(root){
if (root is not empty){
visit root
for each child of root preorder( child )
} }
preorderBT(root){
if (root is not empty){
visit root
preorderBT(root.left)
preorderBT(root.right) }
}
BINARYTREETRAVERSAL (DEPTHFIRST)
preorderBT(root){
if (root is not empty){
visit root
preorderBT(root.left)
preorderBT(root.right) }
}
postorderBT(root){
}
BINARYTREETRAVERSAL (DEPTHFIRST)
preorderBT(root){
if (root is not empty){
visit root
preorderBT(root.left)
preorderBT(root.right) }
}
postorderBT(root){
if (root is not empty){
postorderBT(root.left) postorderBT(root.right) visit root
} }
BINARYTREETRAVERSAL (DEPTHFIRST)
preorderBT(root){
if (root is not empty){
visit root
preorderBT(root.left)
preorderBT(root.right) }
}
postorderBT(root){
if (root is not empty){
postorderBT(root.left) postorderBT(root.right) visit root
} }
inorderBT(root){
if (root is not empty){
visit root preorderBT(root.left) preorderBT(root.right)
}
}
BINARYTREETRAVERSAL (DEPTHFIRST)
preorderBT(root){
if (root is not empty){
visit root
preorderBT(root.left)
preorderBT(root.right) }
}
postorderBT(root){
if (root is not empty){
postorderBT(root.left) postorderBT(root.right) visit root
} }
inorderBT(root){
if (root is not empty){
inorderBT(root.left) visit root inorderBT(root.right)
} }
EXAMPLE
a
Pre order: In order: Post order:
b
c
d
f
g
e
EXAMPLE
a
Pre order: a b d e c f g In order:
Post order:
b
c
d
f
g
e
EXAMPLE
a
Pre order: a b d e c f g In order: d e b a f c g Post order:
b
c
d
f
g
e
EXAMPLE
a
Pre order: In order: Post order:
a b d e c f g d e b a f c g e d b f g c a
b
c
d
f
g
e
EXPRESSIONS TREES
EXPRESSION TREES
e.g. 3 + 4 * 2
3 + (4 * 2)
3
+
*
4
2
EXPRESSION TREES
e.g. 3 + 4 * 2 (3 + 4) * 2
3 + (4 * 2)
*
+
+
2
3
*
3
4
4
2
My Windows calculator says 3 + 4 * 2 = 14.
Why? (3 + 4) * 2 = 14. Whereas….
if I google “3+4*2”, I get 11. 3 + (4*2) = 11.
EXPRESSIONS
We can make expressions using binary operators +, -, *, /, ^ e.g. a – b / c + d * e ^ f ^ g
^ is exponentiation: e ^ f ^ g = e ^ (f ^ g)
We don’t consider unary operators e.g. 3 + -4 = 3 + (-4)
Operator precedence ordering makes brackets unnecessary.
(a – (b / c)) + (d * (e ^ (f ^ g)))
EXPRESSION TREE
a – b / c + d * e ^ f ^ g ≡ (a – (b / c)) + (d ∗ (e ^ (f ^ g)))
+
*
Internal nodes are operators. Leaves are operands.
a
/
d
e
b
c
f
g
EXPRESSION TREE
+
An expression tree can be a way of thinking about the ordering of operations used when evaluating an expression.
But to be concrete, let’s assume we have a binary tree data structure.
*
a
/
d
e
b
c
f
g
EXPRESSION TREE – TRAVERSAL
b
c
+
a
/
d
*
If we traverse an expression tree, and print out the node label, what is the expression printed out?
e
preorder traversal gives:
f
g
EXPRESSION TREE – TRAVERSAL
b
c
+
a
/
d
*
If we traverse an expression tree, and print out the node label, what is the expression printed out?
e
f
preorder traversal gives: + – a / b c * d ^ e ^ f g
g
EXPRESSION TREE – TRAVERSAL
b
c
+
a
/
d
*
If we traverse an expression tree, and print out the node label, what is the expression printed out?
e
f
preorder traversal gives: + – a / b c * d ^ e ^ f g
inorder traversal gives:
g
EXPRESSION TREE – TRAVERSAL
b
c
+
a
/
d
*
If we traverse an expression tree, and print out the node label, what is the expression printed out?
e
f
preorder traversal gives: + – a / b c * d ^ e ^ f g
inorder traversal gives: a – b / c + d * e ^ f ^ g
g
EXPRESSION TREE – TRAVERSAL
b
c
+
a
/
d
*
If we traverse an expression tree, and print out the node label, what is the expression printed out?
e
preorder traversal gives: inorder traversal gives: postorder traversal gives:
+ – a / b c * d ^ e ^ f g a – b / c + d * e ^ f ^ g
f
g
EXPRESSION TREE – TRAVERSAL
b
c
+
a
/
d
*
If we traverse an expression tree, and print out the node label, what is the expression printed out?
e
preorder traversal gives: inorder traversal gives: postorder traversal gives:
+ – a / b c * d ^ e ^ f g a – b / c + d * e ^ f ^ g a b c / – d e f g ^ ^ * +
f
g
PREFIX, INFIX, POSTFIX EXPRESSIONS
*
prefix: infix:
postfix:
* a b a * b
a b *
a
b
PREFIX, INFIX, POSTFIX EXPRESSIONS
baseExp = variable | integer
op =+|-|*|/|^
preExp = baseExp | op preExp preExp
where | means ‘or’
PREFIX, INFIX, POSTFIX EXPRESSIONS
baseExp = variable | integer
op =+|-|*|/|^
preExp = baseExp | op preExp preExp
Use inExp = baseExp | inExp op inExp only one.
postExp = baseExp | postExp postExp op
EXPRESSION TREE – TRAVERSAL
b
c
+
a
/
d
*
If we traverse an expression tree, and print out the node label, what is the expression printed out?
e
preorder traversal gives prefix expression: inorder traversal gives infix expression: postorder traversal gives postfix expression:
+ – a / b c * d ^ e ^ f g a – b / c + d * e ^ f ^ g a b c / – d e f g ^ ^ * +
f
g
TERMINOLOGY
Prefix expressions called “Polish Notation” (after Polish logician Jan Lucasewicz 1920’s)
Postfix expressions are called “Reverse Polish notation” (RPN)
Some calculators (esp. Hewlett Packard) require users to input expressions using RPN.
TERMINOLOGY
Prefix expressions called “Polish Notation” (after Polish logician Jan Lucasewicz 1920’s)
Postfix expressions are called “Reverse Polish notation” (RPN) Calculate 5 * 4 + 3 :
5
No “=“ symbol on keyboard.
In the next videos: Binary Search Trees Heaps