Lecture Notes on Lists II and Binary Trees (COMP11120)

More on Lists, and Introduction to Binary Trees

Binary Trees

Terminology
L root
in a
binary tree every mode >
- in a full binary tree
, every node


7
has at most 2 children
. ·
is either a leaf

leaves & · or has a left and right child , which themselves are the root of a tree.


full binary tree
T 7 in a
every node

has 0 or 2 children
. - a full binary tree consists of


· either just a root mode


· or a root and a left and a right (subtree.




Full Binary Trees
Definition A full binary tree with labels from set S base Step case
: a is given
by case




basecase trees where seS tree S 7 S treeg (t t) ,
> S
,



Step case Given trees t ,
t with labels from S
, t t

treeg (t ,
tl) is a tree with labels from S
.




Example : trees (treen (troes treez) , , treed


3
#
*
-
H 04
#

3 28
↑




FBTreess : set of all full binary trees with labels from S
.



Example Define
: operation FBTreess <
IN that returns the height of Example : Give an operation no :
FiTreess > 11I that returns the
tree number of nodes tree
a .

of a .




base case Light (trees) = D base case noltroos) =
1

Step case Light (trees (t t)) ,
= 1 + max light , light ↑
Step case no(troeg(t ,
t) = not + not + 1




Example : Show that for all to FBTroesg ,
light not Example : Show that for te FBTreesg ,
not is old




base case Light trees = 0 1 = no trees base case noltrees) = 1 which is odd


Step case
hight (treeg(t t ,
=
1 + max (lightt lightt) , ind .
hyp not , not' are odd
max(a, b) ( a + b

& 1 +
light + lightt Step case nol trees (t t) = 1 + not + not
,


not not E *

>
- 1 + + indhyp by ind .
hyp . We can find i
,
je IN such that

= no (trees (t , tl) not = 2i + 1


not =
2j + 1

L


= 1 + 2i + 1 + 2j1
= 1 + 2(i + j +
1)
↓
=
1 + even


= odd