Transcript Complete Binary Trees

Complete Binary Trees
Chapter 10 introduces trees.
 This presentation illustrates the
simplest kind of trees: Complete
Binary Trees.

Data Structures
and Other Objects
Using C++
Trees

First example of nonlinear structure
Do not form a simple sequence of first entry, second
entry, ……
 More complex linking between the components

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
node.
 But it is the connections between the nodes which
characterize a binary tree.

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
node.
 But it is the connections between the nodes which
characterize a binary tree.

An example can
illustrate how the
connections work
A Binary Tree of States
In this example,
the data
contained at
each node is
one of the 50
states.
Washington
Arkansas
Colorado
Arizona
Florida
Massachusetts
Oklahoma
A Binary Tree of States
Each tree has a
special node
called its root,
usually drawn
at the top.
Washington
Arkansas
Colorado
Arizona
Florida
Massachusetts
Oklahoma
A Binary Tree of States
Each tree has a
special node
called its root,
usually drawn
at the top.
Washington
Arkansas
Colorado
Arizona
Florida
Massachusetts
The example tree
Oklahoma has Washington
as its root.
A Binary Tree of States
Each node is
permitted to
have two links
to other nodes,
called the left
child and the
right child.
Washington
Arkansas
Colorado
Arizona
Florida
Massachusetts
Oklahoma
A Binary Tree of States
Each node is
permitted to
have two links
to other nodes,
called the left
child and the
right child.
Washington
Arkansas
Colorado
Arizona
Florida
Massachusetts
Oklahoma
A Binary Tree of States
Children are
usually drawn
below a node.
Washington
Arkansas
Colorado
Arizona
The left child of
Florida
Washington
is
Arkansas.
Massachusetts
The right child of
Oklahoma Washington is
Colorado.
A Binary Tree of States
Some nodes
have only one
child.
Washington
Arkansas
Colorado
Arizona
Florida
Arkansas has a
left child, but no
right child. Massachusetts
Oklahoma
A Quiz
Some nodes
have only one
child.
Washington
Arkansas
Colorado
Arizona
Florida
Which node has
only a right child?
Massachusetts
Oklahoma
A Quiz
Washington
Some nodes
have only one
child.
Arkansas
Colorado
Arizona
Florida
Florida has
only a right child.
Massachusetts
Oklahoma
A Binary Tree of States
A node with no
children is
called a leaf.
Washington
Arkansas
Colorado
Arizona
Florida
Massachusetts
Oklahoma
A Binary Tree of States
Each node is
called the
parent of its
children.
Washington
Arkansas
Colorado
Arizona
Florida
Washington is the
parent of Arkansas
and Colorado. Massachusetts
Oklahoma
A Binary Tree of States
Washington
Two rules about parents:
 The root has no
parent.
 Every other node
has exactly one
parent.
Arkansas
Colorado
Arizona
Florida
Massachusetts
Oklahoma
A Binary Tree of States
Washington
Two nodes with
the same parent
are called
siblings.
Arkansas
Colorado
Arizona
Florida
Arkansas
and Colorado
are siblings.
Massachusetts
Oklahoma
Binary Trees Terminologies









Node
Parent
Children: left and right child
Sibling: have the same parent
Leaf: a node with no children
Ancestor

First ancestor: the node’s parent

Next ancestor: the parent of the parent
Descendant

First descendant: the node’s children

Next descendant: the children’s children
Subtree: left and right subtree
Depth of a node: the number of steps moving up to the parent

Root node is at 0 depth
Binary Trees Terminologies

Depth of a tree


Full binary tree


The maximum depth of any of its leaves
Every leaf has the same depth, and every non-leaf has two children
Complete binary tree


Every level except the deepest must contain as many nodes as
possible
At the deepest level, all the nodes are as far left as possible
Complete Binary Trees
A complete
binary tree is a
special kind of
binary tree
which will be
useful to us.
Complete Binary Trees
A complete
binary tree is a
special kind of
binary tree
which will be
useful to us.
When a complete
binary tree is built,
its first node must be
the root.
Complete Binary Trees
The second node of a
complete binary tree
is always the left
child of the root...
Complete Binary Trees
The second node of a
complete binary tree
is always the left
child of the root...
... and the third node
is always the right
child of the root.
Complete Binary Trees
The next
nodes must
always fill the
next level
from left to
right.
Complete Binary Trees
The next
nodes must
always fill the
next level
from left to
right.
Complete Binary Trees
The next
nodes must
always fill the
next level
from left to
right.
Complete Binary Trees
The next
nodes must
always fill the
next level
from left to
right.
Complete Binary Trees
The next
nodes must
always fill the
next level
from left to
right.
Complete Binary Trees
The next
nodes must
always fill the
next level
from left to
right.
Is This Complete?
Is This Complete?
Is This Complete?
Is This Complete?
Is This Complete?
Yes!
 It is called the empty
tree, and it has no
nodes, not even a root.
Binary Trees

A binary tree is a finite set of nodes. The set might be
empty. But if the set is not empty, it follows these rules:




There is one special node, called the root.
Each node may be associated with up to two other
different nodes.
Each node, except the root, has exactly one parent; the
root has no parent
If you start at a node and move to the node’s parent, then
move again to that node’s parent, and keep moving
upward to each node’s parent, you will eventually reach
the root.
Implementing a Complete Binary
Tree

We will store the date from the nodes
in a partially-filled array.
3
An integer to keep
track of how many nodes are in the tree
An array of data
We don't care what's in
this part of the array.
Implementing a Complete Binary
Tree
R
0
1
2
3
4
5
6
7
8
Implementing a Complete Binary
Tree
R
0
1
2
3
4
5
6
7
8
Implementing a Complete Binary
Tree
R
E
0
1
2
3
4
5
6
7
8
Implementing a Complete Binary
Tree
R
E
C
0
1
2
3
4
5
6
7
8
Implementing a Complete Binary
Tree
R
E
C
U
0
1
2
3
4
5
6
7
8
Implementing a Complete Binary
Tree
R
E
C
U
R
0
1
2
3
4
5
6
7
8
Implementing a Complete Binary
Tree
R
E
C
U
R
S
0
1
2
3
4
5
6
7
8
Implementing a Complete Binary
Tree
R
E
0
1
C
2
U
R
S
I
3
4
5
6
7
8
Implementing a Complete Binary
Tree
R
E
0
1
C
2
U
R
S
I
O
3
4
5
6
7
N
8
Implementing a Complete Binary
Tree
Properties:
1.Root node is at index 0
2.The parent of a node at index i is
at location (i - 1)/2
3.The children of a node at index i
are at 2 * i + 1 and 2 * i + 2
* If those indices are out of
bounds, then the nodes does
not have one or both of those
children
R
E
0
1
C
2
U
R
S
I
O
3
4
5
6
7
N
8
Implementing a Complete Binary
Tree using Nodes
 The node has:
1. Data element
2. Left link
3. Right link
 Tree Operations:
1. Tree size
2. Tree clear
3. Tree copy
Animal Guess Game
Animal Guess Game
Exam the code:
1.Useful functions
1.void eat_line( )
2.bool inquire(const char query[ ])
2.void instruct( )
•Postcondition: Instructions for playing the game have been printed to the screen.
3.binary_tree_node<string>* beginning_tree( )
•Postcondition: The function has created a small binary tree. The return value is the root pointer of the new tree.
4.void play(binary_tree_node<string>* current_ptr)
•Precondition: current_ptr points to the root of a binary tree with at least two leaves.
•Postcondition: One round of the animal game has been played, and maybe the tree has been improved.
5.void ask_and_move(binary_tree_node<string>*& current_ptr)
•Precondition: current_ptr points to a non-leaf node in a binary tree.
•Postcondition: The question at the current node has been asked. The current pointer has been shifted left (if the user answered yes) or
right (for a no answer).
6.void learn(binary_tree_node<string>*& leaf_ptr)
•Precondition: leaf_ptr is a pointer to a leaf in a binary tree. The leaf contains a wrong guess that was just made.
•Postcondition: Information has been elicited from the user, and the tree has been improved.
Implementing a Complete Binary
Tree using Nodes
 Tree traversals
7
1. In-order
2. Pre-order
3. Post-order
 Do not want to rewrite
traversal for every usage
 Pass in usage (function)
as an argument to
traversal function
5
3
2
8
6
4
9
6
template <class BTNode>
void inorder(BTNode* node_ptr)
{
if (node_ptr != NULL)
{
inorder(node_ptr->left( ));
cout << node_ptr->data( ) );
inorder(node_ptr->right( ));
}
}
Function Parameters

Parameter to a function may be a function

void apply(void f(int&), int data[], size_t n)

Precondition: data is an array with at least n components

Post-condition: the function f has been applied to the n components of the data array
Function Parameters
void apply (void f(int&), int data[], size_t n) {
for (size_t i = 0; i < n; ++i)
f(data[i]);
}
void seven_up(int & i){
i += 7;
}
apply(seven_up, numbers, 10);
Template Function Parameters
Template<class Item, class SizeType>
void apply (void f(Item&), Item data[], SizeType n)
{ for (size_t i = 0; i < n; ++i)
f(data[i]);
}
void convert_to_upper(char & c);
apply(convert_to_upper, names, 10);
Further Generalization
Template<class Process, class Item, class SizeType>
void apply (Process f, Item data[], SizeType n) {
for (size_t i = 0; i < n; ++i)
f(data[i]);
}
void triple(int & i);
void print(const string & s);
apply(triple, numbers, 10);
Apply(print, words, 10);
Template Function for Tree
Traversals
Template<class Process, class BTNode>
void preorder (Process f, BTNOde* node_ptr) {
if (node_ptr != NULL)
{
f (node_ptr->data());
preorder(f, node_ptr->left());
preorder(f, node_ptr->right());
}
}
Summary
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
will eventually reach the root.
 Every node except the root has one parent. The
root has no parent.
 Complete binary trees require the nodes to fill in
each level from left-to-right before starting the
next level.
