19
Complete Binary Trees
The second node of a
20
The next node must be the right child of the root.
Complete Binary Trees
The second node of a
complete binary tree
is always the left
21
And so we continue, adding nodes. But in a complete binary tree, the
way that we add nodes is restricted: Nodes must completely fill each
Complete Binary Trees
The next
nodes must
always fill
22
The fifth node must go in the next available spot in this level, which is
the right child of Arkansas.
Complete Binary Trees
The next
nodes must
23
Complete Binary Trees
The next
nodes must
24
…and the right child of Colorado.
Complete Binary Trees
The next
nodes must
25
Complete Binary Trees
The next
nodes must
always fill
26
Complete Binary Trees
The next
nodes must
27
Just to check your understanding, is this binary tree a complete binary
tree?
Is This Complete?
28
Is this complete?
Is This Complete?
29
Is This Complete?
30
Is This Complete?
31
This binary tree is also complete, although you might have to squint to
Is This Complete?
Yes!
32
Implementing a Complete Binary
Tree
❐We will store the date from the nodes
in a partially-filled array.
An integer to keep
track of how many nodes are in the tree
3
33
The solution to this problem is in Section 10.2 of the text, which
discusses several different ways to implement binary trees. The
Implementing a Complete Binary
Tree
❐We will store the date from the nodes
in a partially-filled array.
An integer to keep
track of how many nodes are in the tree
3
34
❐Binary trees contain nodes.
❐Each node may have a left child and a right child.
❐If you start from any node and move upward, you
❐Complete binary trees require the nodes to fill in
each level from left-to-right before starting the
next level.
Summary
35
Presentation copyright 1997 Addison Wesley Longman,
For use with
Data Structures and Other Objects Using C++
by Michael Main and Walter Savitch.
Some artwork in the presentation is used with permission from Presentation Task Force
(copyright New Vision Technologies Inc) and Corel Gallery Clipart Catalog (copyright