Data Structure and Algorithms based on the Object-oriented programming
(OOP) where some are the base of OOP for an instant inheritance,
polymorphism, Encapsulation, and Abstraction, etc. Now we will start learning
data structures in programming languages such as Linked list, arrays, Structs,
Classes, Queues, Stacks, etc.
Today’s Concept:
Binary Trees Data Structure
Prerequisite of
this Lab is all those students who have basic concepts on C++ Programming such
as Syntax of Language, the concept of functions, pointers, data types, etc.
Visual Studio 2012 and onward version will be used for implementation and
programming tasks assigned in the Lab.
Binary Tree Unlike all
the previous data structures Arrays, Linked Lists, Stack, and queues, which are
linear data structures, trees are hierarchical data structures. Trees when using Breath First Search (BFS)
provide moderate search quicker than Linked List and slower than arrays. Trees provide
moderate insertion/deletion quicker than Arrays and slower than Unordered
Linked Lists. Like Linked Lists and unlike Arrays, Trees don’t have an upper
limit on the number of nodes as nodes are linked using pointers this feature is
same as the Lined list and Doubly linked list data structures because all these aforementioned
Data Structures have Pointers which can be increased on run time due to the
dynamic feature.
There are different terms
used in tree data structures such as the topmost node is called the root of the
tree. The elements that are directly under an element are called its children.
The element directly above something is called its parent.
Why Use Tree Data Structures
One of the major reasons to use trees might be because you want to store
information that naturally forms a hierarchy. For example, the file system on a
computer in which you can see a tree-like structure of processes or information stored
or you have an information system that required a tree-like/ hierarchical structure like
designations/ hierarch in organizations. There are many other applications of
Tree data Structures such as Manipulate hierarchical data. Make
information easy to search (see tree traversal). Manipulate sorted lists of
data. As a workflow for compositing digital images for visual effects. Router
algorithms. Form of multi-stage decision-making (see business chess).
Implementation of Deletion in Binary Tree:
//
C++ program to delete element in binary tree
#include <iostream>
using namespace std;
/*
A binary tree node has key, pointer to left
child
and a pointer to right child */
struct Node {
int
key;
struct Node *left, *right;
};
/*
function to create a new node of tree and
return
pointer */
struct Node* newNode(int key)
{
struct Node* temp = new Node;
temp->key = key;
temp->left = temp->right = NULL;
return temp;
};
/*
Inorder traversal of a binary tree*/
void inorder(struct Node* temp)
{
if
(!temp)
return;
inorder(temp->left);
cout << temp->key << " ";
inorder(temp->right);
}
/*
function to delete the given deepest node
(d_node)
in binary tree */
void deletDeepest(struct Node* root,
struct Node* d_node)
{
queue<struct Node*> q;
q.push(root);
// Do level order traversal until last node
struct Node* temp;
while
(!q.empty()) {
temp = q.front();
q.pop();
if
(temp == d_node) {
temp = NULL;
delete (d_node);
return;
}
if
(temp->right) {
if
(temp->right == d_node) {
temp->right = NULL;
delete (d_node);
return;
}
else
q.push(temp->right);
}
if
(temp->left) {
if
(temp->left == d_node) {
temp->left = NULL;
delete (d_node);
return;
}
else
q.push(temp->left);
}
}
}
/*
function to delete element in binary tree */
Node* deletion(struct Node* root, int key)
{
if
(root == NULL)
return NULL;
if
(root->left == NULL && root->right == NULL) {
if
(root->key == key)
return NULL;
else
return root;
}
queue<struct Node*> q;
q.push(root);
struct Node* temp;
struct Node* key_node = NULL;
// Do level order traversal to find deepest
// node(temp) and node to be
deleted (key_node)
while
(!q.empty()) {
temp = q.front();
q.pop();
if
(temp->key == key)
key_node = temp;
if
(temp->left)
q.push(temp->left);
if
(temp->right)
q.push(temp->right);
}
if
(key_node != NULL) {
int
x = temp->key;
deletDeepest(root, temp);
key_node->key = x;
}
return root;
}
//
Driver code
int main()
{
struct Node* root = newNode(10);
root->left = newNode(11);
root->left->left = newNode(7);
root->left->right = newNode(12);
root->right = newNode(9);
root->right->left = newNode(15);
root->right->right = newNode(8);
cout << "Inorder traversal
before deletion : ";
inorder(root);
int
key = 11;
root = deletion(root, key);
cout << endl;
cout << "Inorder traversal
after deletion : ";
inorder(root);
return 0;
}
Binary Trees Insertion Tasks Submission:
Assignment Submission for BFS & DFS implementation:
Post a Comment