CC-213L – Data Structures and Algorithms
Fall 2024
LAB-11 Issue Date: December 9, 2024
The objective of this lab is to:
To familiarize students with the fundamental concepts of tree data structures, including nodes, parent-
child relationships, and hierarchical organization.
To make students implement tree structures using array representation, emphasizing index-based
navigation techniques and understanding the storage efficiency of this approach.
To develop tree structures using linked representations and to contrast this approach with array-based
implementations.
To help students analyze the advantages and disadvantages of array-based versus linked-based
implementations in terms of memory usage, ease of implementation, and flexibility.
Task 01: (Linked Based Implementation) [25 Marks]
Implement the binary tree using linked implementation as we discussed in class.
// forward declaration of template class BTree
template<class T>
class BTree;
// Definition of template class TreeNode
template<class T>
class TreeNode
{
friend BTree<T>;
T data;
TreeNode<T>* left;
TreeNode<T>* right;
// Methods…
};
// Definition of template class BTree
template<class T>
class BTree
{
TreeNode<T>* root;
// Methods…
};
Implement following functions for BTree class:
1. Constructor, destructor, Copy-constructor.
2. void setRoot ( T value );
3. void setLeftChild ( TreeNode<T>* node, T value );
4. void setRightChild ( TreeNode<T>* node, T value );
5. TreeNode<T>* getLeftChild (TreeNode<T>* node);
6. TreeNode<T>* getRightChild (TreeNode<T>* node);
7. void preOrder( );
8. void inOrder( );
9. void postOrder( );
10. void levelOrder( );
11. DNode<T>* search( T val )
Find the value ‘val’ using any traversal. Return null in case value not found or return the node
containing val.
12. void delete ( TreeNode<T>* node )
Deletes the given node and all its decedents.
Punjab University College Of Information Technology Page 1 of 2
Madiha Khalid
CC-213L – Data Structures and Algorithms
Fall 2024
LAB-11 Issue Date: December 9, 2024
Task 02: (Array Based Implementation) [25 marks]
Implement the binary tree using arrays as discussed in the class. In array based implementation there may be
following questions to be answered:
What is the initial size of array as the tree starts growing from root to leaf node by node?
You can take height of the tree as input and can find the maximum possible nodes of given height
using 2h – 1. So you can create the array of maximum possible nodes of a given height and store
the tree nodes in level order.
How to get children of a particular node?
On examining a tree and its array you may observe that all left children are on odd indices and all
right children are on even indices. Thus, for each node at index 𝑖, the left child is at index (2 ×
𝑖) + 1, and the right child is at index (2 × 𝑖) + 2. The parent of node 𝑖 is at ⌊(𝑖 − 1)/2⌋.
You may use following class definition and implement the functions given in the public part of the Tree.
You may write other utility functions if you think required.
template<class T>
class BinaryTree
{
private:
int height; // represent the maximum possible height of the tree.
T* data; // stores the tree nodes.
bool* status; // this array is used to find that whether there is a
// node on a particular index or not. If there is a valid
// node exitsts on a particular index the status array holds
// 'true' on corresponding index.
public:
BinaryTree(int h);//creates & initializes the status & data array of size 2h-1.
~BinaryTree();
void setRoot(T val); // set val at data[0] and set status[0] = true;
T getRoot(); // returns the root of tree if exists.
void setLeftChild(T parent, T val); // sets tge left child of given Parent.
void setRightChild(T parent, T val);
int getParent(int node); // returns the index of parent node.
int getLeftChild (int par); // returns the index of leftChild of index ‘par’
int getRightChild (int par);
void remove(T node); // remove the given node and all its descendants.
void preOrder(); // display tree nodes using preOrder Traversal.
void postOrder(); // display tree nodes using postOrder Traversal.
void inOrder(); // display tree nodes using inOrder Traversal.
void levelOrder(); // display tree nodes using levelOrder Traversal.
void displayAncestors(T node);
void displayDescendents(T node);
bool isPerfectTree(); // returns true if the tree is perfect, otherwise false.
bool iscompleteTree(); // returns true if the tree is perfect, otherwise false.
};
Remember!
Write a proper main program as part of your project, providing menu to make it easy to test your
functions.
Punjab University College Of Information Technology Page 2 of 2
Madiha Khalid
