Transcript Presentation on Implementing Binary Trees

5. Abstract Data
Structures & Algorithms
5.3 Dynamic Data Structures
1
5.3.8 Implementing Binary Trees Dynamically
Approach
• As with linked lists, write a class to create the
nodes and their properties, but including two
pointers (left and right).
‣
public class Student () {
public String name = null;
public int age = -1;
public Student left = null;
public Student right = null;
}
3
Approach
• Since there is never a need to insert a node in
the middle of a binary tree, the only
constructor methods needed are for:
‣
‣
a blank node (this would effectively blank
the tree if put into root) and
one for a terminal node (with no pointers).
4
Approach
• If the root node is empty, create it first
(compare with front of a linked list).
• Since any tree is made of smaller and
smaller subtrees, recursion can be used.
• Deal with any base cases first.
5
Insert a node
• Create a temporary node to act as a runner
as you traverse the tree and point runner at
root.
• Check if the tree is empty (root
= null), in
which case put the new node into root) - the
base case.
• Check if the new node belongs left or right
from the runner, then....
6
Insert a node
• Call this method recursively (effectively
redefining this node as root), such that if the
node pointed at is empty (base case) the new
node is inserted, if not, check whether new
node belongs left or right and then...
7
Insert a node
• Call this method recursively (effectively
redefining this node as root), such that if the
node pointed at is empty (base case) the new
node is inserted, if not, check whether new
node belongs left or right and then...
• (this repeats until base case is met)
8
Counting nodes
• Count the total number of nodes present in
the tree again by traversing the whole tree,
adding 1 to a counter every time you
encounter a node that is not empty and return
the final count.
• Again, note the recursive call and the
redefinition of root for each sub tree.
9
Outputting nodes
• Same pattern of traversal as for counting
nodes
• Outputting: use a print statement instead of a
counter and no return type.
10
Presence/search
• Presence check (checking if a node is
actually in the tree) - immediately the required
node is encountered, return true.
• Search: similar to presence check, only return
the node itself.
11