1
This lecture is an introduction to trees, illustrating basic terminology for
binary trees, and focusing on complete binary
❐Chapter 10 introduces trees.
❐This presentation illustrates the
Complete Binary Trees
Data Structures
and Other Objects
Using C++
2
Binary Trees
❐A binary tree has nodes, similar to nodes in a
linked list structure.
3
But, unlike a linked list, the connections between the nodes are more
Binary Trees
❐A binary tree has nodes, similar to nodes in a
linked list structure.
❐Data of one sort or another may be stored at each
4
A Binary Tree of States
In this example,
the data
5
A Binary Tree of States
Each tree has a
special node
6
In this example, Washington State is at the root.
A Binary Tree of States
Each tree has a
as its root.
7
A Binary Tree of States
Each node is
permitted to
have two links
8
A Binary Tree of States
Each node is
permitted to
9
A Binary Tree of States
Children are
usually drawn
10
A Binary Tree of States
Some nodes
have only one
child.
11
A Quiz
Some nodes
have only one
child.
12
A Quiz
Some nodes
have only one
child.
13
Some nodes have no children, and those nodes are called leaves. In
A Binary Tree of States
A node with no
children is
14
A Binary Tree of States
Each node is
15
There are two rules about parents in any tree:
A Binary Tree of States
Two rules about parents:
❶The root has no
parent.
16
A Binary Tree of States
Two nodes with
17
Complete Binary Trees
A complete
binary tree is a
special kind of
binary tree
18
Complete Binary Trees
A complete
binary tree is a
special kind of
binary tree
which will be