Binary Tree | Inorder, Preorder, Postorder Recursive and Non-Recursive Traversal | Mirror Binary Tree | Height of Tree | Cloning Binary Tree | Number of Leaves | Number of Internal Nodes | Erasing all nodes of Binary Tree
Problem Statement: Beginning with an empty binary tree, construct a binary tree by inserting the values in the order given. After constructing a binary tree perform the following operations on it-
- Perform inorder, preorder and postorder traversal (Implement both recursive and non-recursive methods)
- Change a tree so that the roles of the left and right pointers are swapped at every node
- Find the height of the tree
- Copy this tree to another
- Count number of leaves, number of internal nodes.
- Erase all nodes in a binary tree
Note:- Scroll horizontally to see the full line of code.
#include <iostream>
using namespace std;
class node
{
// data members
public:
int data;
node *left;
node *right;
// node constructor
node(int val)
{
data = val;
}
};
class nodePointer
{
public:
node *link;
int flag = 0;
};
class nodeStack
{
nodePointer *nodes;
int top;
public:
nodeStack()
{
nodes = new nodePointer[30];
top = -1;
}
void push(node *x, int n = 0)
{
if (!full())
{
top++;
nodes[top].link = x;
nodes[top].flag = n;
}
}
node *Top()
{
if (!isEmpty())
{
return nodes[top].link;
}
else
{
return NULL;
}
}
int TopFlag()
{
if (!isEmpty())
{
return nodes[top].flag;
}
else
{
return -1;
}
}
void pop()
{
if (!isEmpty())
{
top--;
}
else
{
cout << "Stack is already empty!";
}
}
bool full()
{
if (top == 29)
{
return true;
}
else
{
return false;
}
}
bool isEmpty()
{
if (top == -1)
{
return true;
}
else
{
return false;
}
}
};
node *createBinaryTree()
{
node *root;
cout << "Enter Data: ";
int val;
cin >> val;
if (val == -1)
{
return NULL;
}
root = new node(val);
cout << "Enter left for " << val << " :" << endl;
root->left = createBinaryTree();
cout << "Enter right for " << val << " :" << endl;
root->right = createBinaryTree();
return root;
}
void preorder(node *root)
{
if (root)
{
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
}
void preorderNonRecursive(node *root)
{
nodeStack Pointers;
if (root)
{
node *current = root;
while (current || !Pointers.isEmpty())
{
if (!current && !Pointers.isEmpty())
{
current = Pointers.Top();
Pointers.pop();
current = current->right;
}
else
{
cout << current->data << " ";
Pointers.push(current);
current = current->left;
}
}
}
}
void postorder(node *root)
{
if (root)
{
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
}
void postorderNonRecursive(node *root)
{
nodeStack Pointers;
node *current = root;
while (current || !Pointers.isEmpty())
{
if (!current && !Pointers.isEmpty())
{
current = Pointers.Top();
if (Pointers.TopFlag() == 0)
{
Pointers.pop();
Pointers.push(current, 1);
current = current->right;
}
else if (Pointers.TopFlag() == 1)
{
cout << current->data << " ";
Pointers.pop();
current = NULL;
}
}
else
{
Pointers.push(current, 0);
current = current->left;
}
}
}
void inorder(node *root)
{
if (root)
{
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
void inorderNonRecursive(node *root)
{
nodeStack Pointers;
if (root)
{
node *current = root;
while (current != NULL || !Pointers.isEmpty())
{
if (current == NULL && !Pointers.isEmpty())
{
current = Pointers.Top();
Pointers.pop();
cout << current->data << " ";
current = current->right;
}
else
{
Pointers.push(current);
current = current->left;
}
}
}
else
{
cout << "Tree is empty" << endl;
}
}
int btHeight(node *root)
{
if (!root)
{
return -1;
}
else
{
int leftBTHeight = btHeight(root->left);
int rightBTHeight = btHeight(root->right);
return (leftBTHeight > rightBTHeight ? leftBTHeight : rightBTHeight) + 1;
}
}
node *swapBT(node *root)
{
if (!root)
{
return NULL;
}
else
{
root->left = swapBT(root->left);
root->right = swapBT(root->right);
node *temp = root->left;
root->left = root->right;
root->right = temp;
return root;
}
}
int leafNodes(node *root)
{
if (!root)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
else
return (leafNodes(root->left) + leafNodes(root->right));
}
int internalNode(node *root)
{
if (!root || (!root->left && !root->right))
{
return 0;
}
else
return (1 + (internalNode(root->left) + internalNode(root->right)));
}
void deleteTree(node *root)
{
if (!root)
{
return;
}
deleteTree(root->left);
deleteTree(root->right);
cout << "Deleting node: " << root->data << endl;
delete root;
}
node *cloneBinaryTree(node *root)
{
if (root == NULL)
{
return NULL;
}
node *root_copy = new node(root->data);
root_copy->left = cloneBinaryTree(root->left);
root_copy->right = cloneBinaryTree(root->right);
return root_copy;
}
int main()
{
node *root;
char cont = 'y';
while (cont == 'y')
{
int choice;
cout << "<----Menu---->" << endl;
cout << "1.Create Binary Tree" << endl;
cout << "2.Inorder Traversal" << endl;
cout << "3.Preorder Traversal" << endl;
cout << "4.Postorder Traversal" << endl;
cout << "5.Leaf Node" << endl;
cout << "6.Internal Nodes" << endl;
cout << "7.Height of Tree" << endl;
cout << "8.Clone Tree" << endl;
cout << "9.Swap Nodes" << endl;
cout << "10.Delete Tree" << endl;
cout << "Enter the Choice: ";
cin >> choice;
switch (choice)
{
case 1:
root = createBinaryTree();
cout << "Tree Created Successfully" << endl;
break;
case 2:
int choice1;
cout << "1. Recursive Inorder" << endl;
cout << "2. Non Recursive Inorder" << endl;
cout << "Enter the choice: ";
cin >> choice1;
switch (choice1)
{
case 1:
cout << "Inorder Traversal: ";
inorder(root);
cout << endl;
break;
case 2:
cout << "Inorder NonRecursive: ";
inorderNonRecursive(root);
cout << endl;
break;
default:
cout << "INVALID CHOICE." << endl;
break;
}
break;
case 3:
int choice2;
cout << "1. Recursive Preorder" << endl;
cout << "2. Non Recursive Preorder" << endl;
cout << "Enter the choice: ";
cin >> choice2;
switch (choice2)
{
case 1:
cout << "Preorder Traversal: ";
preorder(root);
cout << endl;
break;
case 2:
cout << "Preorder NonRecursive: ";
preorderNonRecursive(root);
cout << endl;
break;
default:
cout << "INVALID CHOICE." << endl;
break;
}
break;
case 4:
int choice3;
cout << "1. Recursive Postorder" << endl;
cout << "2. Non Recursive Postorder" << endl;
cout << "Enter the choice: ";
cin >> choice3;
switch (choice3)
{
case 1:
cout << "Postorder Traversal: ";
postorder(root);
cout << endl;
break;
case 2:
cout << "Inorder NonRecursive: ";
postorderNonRecursive(root);
cout << endl;
break;
default:
cout << "INVALID CHOICE." << endl;
break;
}
break;
case 5:
cout << "No. of Leaf Nodes: " << leafNodes(root) << endl;
break;
case 6:
cout << "No. of Internal Nodes: " << internalNode(root) << endl;
break;
case 7:
cout << "Height of Tree: " << btHeight(root) << endl;
break;
case 8:
node *clonetree;
clonetree = cloneBinaryTree(root);
cout << "Tree copied Successfully" << endl;
cout << "Inorder Traversal of Clone Tree: ";
inorder(clonetree);
cout << endl;
break;
case 9:
root = swapBT(root);
cout << "Inorder Traversal after mirroring: ";
inorder(root);
cout << endl;
break;
case 10:
deleteTree(root);
cout << "Tree Deleted Successfully!" << endl;
break;
default:
cout << "INVALID CHOICE!!!" << endl;
break;
}
cout << "Do yo want to continue? (y/n): ";
cin >> cont;
}
cout << "Program Ended Successfully!!!" << endl;
return 0;
}
Comments
Post a Comment