Chapter 16
Tree Implementations
CENG 214
Algorithms &
Data Structures 2
Nodes in a Binary Tree
• Representing tree nodes
– Must contain both data and "pointers" to node’s
children
– Each node will be an object
• Array-based
– Pointers will be array indices
• Link-based
– Use C++ pointers
Alg.-2 2/85
Array-Based Representation
• Class of array-based data members
– Variable root is index to tree’s root node within
the array tree
– If tree is empty, root = -1
Alg.-2 3/85
Array-Based Representation
• As tree changes (additions, removals) …
– Nodes may not be in contiguous array elements
• Thus, need list of available nodes
– Called a free list
• Node removed from tree
– Placed in free list for later use
Alg.-2 4/85
Array-Based Representation
• The class TreeNode for an array-based
implementation of the ADT binary tree
Alg.-2 5/85
Array-Based Representation
(a) A binary tree of names;
(b) Its implementation
using the array tree
Alg.-2 6/85
Link-Based Representation
• The header file containing the class BinaryNode for a
link-based implementation of the ADT binary tree
Alg.-2 7/85
Link-Based Representation
• The header file containing the class BinaryNode for a
link-based implementation of the ADT binary tree
Alg.-2 8/85
Link-Based Representation
• A link-based implementation of a binary tree
Alg.-2 9/85
Sample uses of public constructors
The public section declares more constructors than we have in the
past, allowing a client to define binary trees in a variety of
circumstances. For example, you can construct a binary tree
• That is empty
• From data for its root, which is its only node
• From data for its root and from its two subtrees
For example, the following statements invoke these 3 constructors:
BinaryNodeTree<string> tree1;
BinaryNodeTree<string>* tree2Ptr = new BinaryNodeTree<string>("A");
BinaryNodeTree<string>* tree3Ptr = new BinaryNodeTree<string>("B");
BinaryNodeTree<string>* tree4Ptr =
new BinaryNodeTree<string>("C", tree2Ptr, tree3Ptr);
Alg.-2 10/85
The Header File
• A header file for the link-based
implementation of the class BinaryNodeTree
Alg.-2 11/85
The Header File
• A header file for the link-based
implementation of the class BinaryNodeTree
Alg.-2 12/85
The Header File
• A header file for the link-based
implementation of the class BinaryNodeTree
Alg.-2 13/85
The Header File
• A header file for the link-based
implementation of the class BinaryNodeTree
Alg.-2 14/85
The Header File
• A header file for the link-based
implementation of the class BinaryNodeTree
Alg.-2 15/85
The Header File
An overloaded assignment operator in the class
BinaryNodeTree
Alg.-2 16/85
The Header File
std::visit is a runtime polymorphic function that
determines the type of the variant object at runtime
and then calls the appropriate function overload.
See visit.cpp
In this example, we define three overloaded
functions: func(int), func(double), and func(const
std::string&). We then create a vector of
std::variant<int, double, std::string> and initialize it
with three elements of different types.
Alg.-2 17/85
The Implementation
The constructors: The public constructors have the following
definitions in the implementation file:
Alg.-2 18/85
The Implementation
• Protected method copyTree called by copy constructor
Alg.-2 19/85
The Implementation
Copy constructor
Alg.-2 20/85
The Implementation
• destroyTree used by destructor which simply
calls this method
Alg.-2 21/85
The Implementation
• Protected method getHeightHelper
Alg.-2 22/85
The Implementation
• Method add
Alg.-2 23/85
balancedAdd method
template<class ItemType>
auto BinaryNodeTree<ItemType>::balancedAdd(std::shared_ptr<BinaryNode<ItemType>>
subTreePtr, std::shared_ptr<BinaryNode<ItemType>> newNodePtr)
{
if (subTreePtr == nullptr)
return newNodePtr;
else
{
auto leftPtr = subTreePtr->getLeftChildPtr();
auto rightPtr = subTreePtr->getRightChildPtr();
if (getHeightHelper(leftPtr) > getHeightHelper(rightPtr))
{
rightPtr = balancedAdd(rightPtr , newNodePtr);
subTreePtr->setRightChildPtr(rightPtr );
}
else
{
leftPtr = balancedAdd(leftPtr, newNodePtr);
subTreePtr->setLeftChildPtr(leftPtr);
} // end if
return subTreePtr;
} // end if
} // end balancedAdd
Alg.-2 24/85
The Implementation
• Adding nodes to an initially empty binary tree
Alg.-2 25/85
The Implementation
• Adding nodes to an initially empty binary tree
Alg.-2 26/85
The Implementation of CPP Codes
Adding sequentially the nodes; 10-20-30-40-50-60-70-80
10 10 10 10
20 20 30 20 30
40
10 10
10
20 30 30
20 20 30
40 60 50
40 80
50 40 60 50
70
Alg.-2 27/85
The traversals
• Since the traversals are recursive, the public
traversal methods each call a protected
method that performs the actual recursion.
• inorder has the function visit which enables
the client not only to examine the item but
also to modify it,
• The second parameter of inorder is the pointer
treePtr which, due to the recursive calls,
eventually points to every node in the tree.
Alg.-2 28/85
A Nonrecursive traversal
• Nonrecursive traversal: Before leaving the topic of
traversals, let’s develop a nonrecursive traversal
algorithm to illustrate further the relationship between
stacks and recursion that was discussed in Stack (Ch.6).
• The definition of inorder follows;
Alg.-2 29/85
The Implementation, recursive
Protected method that enables recursive traversals
Alg.-2 30/85
The Implementation
Contents of the implicit stack as treePtr progresses through
a given tree during a recursive inorder traversal
Alg.-2 31/85
The Implementation
(a) the left subtree
(steps 9 and 10 in
previous figure)
Alg.-2 32/85
The Implementation
(b) the right
subtree of 20
(inorder traversal)
Alg.-2 33/85
A Nonrecursive traversal
2 facts emerge from the recursive version of inorder when a
return is made from a recursive call:
I. The implicit recursive stack of pointers is used to find the
node p that the traversal must go back to.
II. Once the traversal backs up to node p , it either visits p or
backs farther up the tree. It visits p if p ’s left subtree has just
been traversed; it backs up if its right subtree has just been
traversed.
You could directly mimic this action by using an iterative method
and an explicit stack, as long as some bookkeeping device kept
track of which subtree of a node had just been traversed.
Good exam question
Alg.-2 34/85
A Nonrecursive traversal
This strategy of not returning to a node after its right
subtree has been traversed is simple to implement:
You place a pointer to a node in the stack only before
the node’s left subtree is traversed, but not before its
right subtree is traversed.
Alg.-2 35/85
The Implementation
Avoiding
returns to
nodes B and C
Alg.-2 36/85
The Implementation
• Nonrecursive inorder traversal
Alg.-2 37/85
The Implementation
• Non-recursive inorder traversal
Alg.-2 38/85
Link-Based Implementation of the ADT
Binary Search Tree
Link-Based Implementation of the ADT Binary Search Tree
• Uses same node objects as for binary-tree
implementation
• Class BinaryNode from Listing16-2 will be used
• Recursive search algorithm from Section15.3.2
is basis for operations
Alg.-2 40/85
Link-Based Implementation of the ADT Binary Search Tree
Adding a new entry: Insert a new entry into a binary search tree
in the same place. Ex: Adding Kody to a binary search tree
Alg.-2 41/85
Link-Based Implementation of the ADT Binary Search Tree
• Method add
– The method creates a new node and passes pointers to the
tree and the new node to a recursive method that actually
performs the insertion.
Alg.-2 42/85
Link-Based Implementation of the ADT Binary Search Tree
• Refinement of insertion algorithm
Alg.-2 43/85
Link-Based Implementation of the ADT Binary Search Tree
(a) Insertion into an empty tree;
(b) Search for Frank terminates at a leaf;
Alg.-2 44/85
Link-Based Implementation of the ADT Binary Search Tree
(c) Insertion at leaf
Alg.-2 45/85
Link-Based Implementation of the ADT Binary Search Tree
First draft of the removal algorithm
Alg.-2 46/85
Link-Based Implementation of the ADT Binary Search Tree
• The essential task here is to remove the target from
the tree. Assuming that removeValue locates the
target in a particular node N , there are three cases
to consider:
• N is a leaf
• N has only one child
• N has two children
Alg.-2 47/85
Link-Based Implementation of the ADT Binary Search Tree
• Cases for node N containing item to be removed
1. N is a leaf
– Remove leaf containing target
– Set pointer in parent to nullptr
Alg.-2 48/85
Link-Based Implementation of the ADT Binary Search Tree
• Cases for node N containing item to be removed
2. N has only left (or right) child – cases are symmetrical
– After N removed, all data items rooted at L (or R) are
adopted by root of N
– All items adopted are in correct order, binary search tree
property preserved
Alg.-2 49/85
Link-Based Implementation of the ADT Binary Search Tree
• Case 2 for removeValue: The data item to remove
is in a node N that has only a left child and whose
parent is node P
Alg.-2 50/85
Link-Based Implementation of the ADT Binary Search Tree
• Case 2 for removeValue: The data item to remove
is in a node N that has only a left child and whose
parent is node P
Alg.-2 51/85
Link-Based Implementation of the ADT Binary Search Tree
• Cases for node N containing item to be removed
3. N has two children
I. Locate another node M easier to remove from tree than N
II. Copy the item that is in M to N , thus effectively removing
from the tree the item originally in N .
III. Remove the node M from the tree.
Alg.-2 52/85
Link-Based Implementation of the ADT Binary Search Tree
• Case 3: The data item to remove is in a node N that
has two children
Alg.-2 53/85
Link-Based Implementation of the ADT Binary Search Tree
(a) Not any node will do; (b) no longer a binary search tree
Alg.-2 54/85
Link-Based Implementation of the ADT Binary Search Tree
Search key x can be replaced by y
Alg.-2 55/85
Link-Based Implementation of the ADT Binary Search Tree
You can copy into N either the item that is immediately after N
’s entry or the item that is immediately before it.
Suppose that, arbitrarily, you decide to use the node whose
entry y comes immediately after N ’s entry x.
This entry is called x ’s inorder successor
Alg.-2 56/85
Link-Based Implementation of the ADT Binary Search Tree
Inorder successor of N’s entry is in the leftmost node in N’s right subtree
Alg.-2 57/85
Link-Based Implementation of the ADT Binary Search Tree
Final draft of the removal algorithm, removeValue
Alg.-2 58/85
Link-Based Implementation of the ADT Binary Search Tree
Final draft of the removal algorithm, removeNode
Alg.-2 59/85
Link-Based Implementation of the ADT Binary Search Tree
• Final draft of the removal algorithm
Alg.-2 60/85
Link-Based Implementation of the ADT Binary Search Tree
Final draft of the removal algorithm, removeLeftMostNode
Alg.-2 61/85
Link-Based Implementation of the ADT Binary Search Tree
• Final draft of the removal algorithm
Alg.-2 62/85
Link-Based Implementation of the ADT Binary Search Tree
• Recursive removal of node N
Alg.-2 63/85
Link-Based Implementation of the ADT Binary Search Tree
• Recursive removal of node N
Alg.-2 64/85
Link-Based Implementation of the ADT Binary Search Tree
• Recursive removal of node N
Alg.-2 65/85
Link-Based Implementation of the ADT Binary Search Tree
• Algorithm for findNode
Alg.-2 66/85
The Class BinarySearchTree (BST)
The Class BinarySearchTree
• A header file for the link-based
implementation of the class BinarySearchTree
Alg.-2 68/85
The Class BinarySearchTree
• A header file for the link-based
implementation of the class BinarySearchTree
Alg.-2 69/85
The Class BinarySearchTree
• A header file for the link-based
implementation of the class BinarySearchTree
Alg.-2 70/85
The Class BinarySearchTree
• A header file for the link-based
implementation of the class BinarySearchTree
Alg.-2 71/85
The Class BinarySearchTree(BST)
• A header file for the link-based
implementation of the class BinarySearchTree
Alg.-2 72/85
Saving a Binary Search Tree in a File
• An initially empty binary search tree after the
addition of 60, 20, 10, 40, 30, 50, and 70
Alg.-2 73/85
Saving a Binary Search Tree in a File
• Saving a binary search tree and then restoring it to
its original shape. Use preorder traversal to save
binary search tree in a file; restore to original shape
by using method add
o The first algorithm restores a binary search tree to exactly the
same shape it had before it was saved.
o For example, If you save the tree in preorder in previous
Figure, you get the sequence 60, 20, 10, 40, 30, 50, 70.
o If you then use the add method to insert these values into a
binary search tree that is initially empty, you will get the
original tree.
Alg.-2 74/85
Saving a Binary Search Tree in a File
• Saving a binary search tree and then restoring it to
a balanced shape: After you save a binary search
tree in a file, do you necessarily want the restored
tree to have its original shape? Maybe or not?
o Recall that you can use a given set of data items to create
several binary search trees with different shapes.
o Although the shape of a binary search tree has no effect
whatsoever on the correctness of the ADT operations, it
will affect the efficiency of those operations.
o Efficient operations are ensured if the binary search tree is
balanced. Balanced binary search tree increases efficiency
of ADT operations
Alg.-2 75/85
Saving a Binary Search Tree in a File
Building a minimum-height full binary search tree;
• A full tree with exactly n = 2 h – 1 nodes for some height h has
the exact middle of the data items in its root.
readTree(treePtr: BinaryNodePointer, n: integer): BinaryNodePointer
if (n > 0) {
treePtr = pointer to new node with nullptr as its child
pointers
// Construct the left subtree
leftPtr = readTree(treePtr->getLeftChildPtr(), n / 2)
treePtr->setLeftChildPtr(leftPtr)
Alg.-2 76/85
Saving a Binary Search Tree in a File
• Building a minimum-height binary search tree
// Get the root
rootItem = next item from file
treePtr->setItem(rootItem)
// Construct the right subtree
rightPtr = readTree(treePtr->getRightChildPtr(), (n - 1) / 2)
treePtr->setRightChildPtr(rightPtr)
return treePtr
}
else
return nullptr
Alg.-2 77/85
Saving a Binary Search Tree in a File
A full tree saved in a file by using inorder traversal,
– If you save a full tree in a file by using an inorder traversal, the
file will be in sorted order,
40
20 60
10, 20, 30, 40, 50, 60, 70
File
10 30 50 70
Alg.-2 78/85
Saving a Binary Search Tree in a File
• A tree of minimum height that is not complete
Alg.-2 79/85
Saving a Binary Search Tree in a File
Question. Consider the pseudocode operation readTree.
a. What binary search tree results when you execute readTree
with a file of the six integers 2, 4, 6, 8, 10, 12?
b. Is the resulting tree’s height a minimum? Is the tree complete?
Is it full?
a. b. The tree has
minimum height and is
complete but not full.
Let’s see cpp codes
Alg.-2 80/85
Tree Sort
• Tree sort uses a binary search tree (bst).
An inorder traversal of the binary search tree bst visits
the integers in bst’s nodes in ascending order
Alg.-2 81/85
General Trees
• A general tree or an n-ary tree with n = 3
Alg.-2 82/85
General Trees
• An implementation of the n-ary tree
Alg.-2 83/85
General Trees
(a) A link-based implementation of the general
tree in previous Figure.
Alg.-2 84/85
General Trees
(b) the
binary tree that part
a represents
Alg.-2 85/85
