程序代写代做代考 data structure C COMP 250

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 root;
:
class BTNode{
T element;
BTNode leftchild;
BTNode rightchild;
: }
}

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
} }

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
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

PREFIX, INFIX, POSTFIX EXPRESSIONS
*
prefix: infix:
postfix:
* a b a * b
a b *
a
b

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 4 * 3 +
No “=“ symbol on keyboard.

In the next videos: Binary Search Trees  Heaps

Related Posts