Project: Binary Tree ADT
Transformers:
1. Add Node (You may follow BST rules for adding and deleting)
2. Delete Node
Observers:
1. Node Count
2. isRoot
3. isParent
4. isChild
5. isSibling
6. isAncestor
7. isDescendant
8. isLeaf
9. Indegree
10. Outdegree
11. Traversals (pre, in, post, level-order)
.CPP CODE
#include<stdio.h>
#include <iostream>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#include "binarytree.h"
using namespace std;
int main()
{
BinaryTree b;
int ch,tmp,ch2;
do
{
system("cls");
cout<<" ---------------------- "<<" Binary Tree Operations"<<" ---------"<<"--------------------- "<<endl;
cout<<" ---------------------- "<<"--- Press 0 to Exit ---"<<" ---------"<<"--------------------- "<<endl;
cout<<endl;
cout<<" 1. Add Node "<<"\t\t\t"<<" 5. Sibling"<<"\t\t"<<" 9. Indegree "<<endl;
cout<<" 2. Delete Node "<<"\t\t"<<" 6. Descendant "<<"\t\t"<<" 10. Outdegree "<<endl;
cout<<" 3. Traversals "<<"\t\t\t"<<" 7. Leaf "<<"\t\t"<<" 11. NodeCount "<<endl;
cout<<" 4. Parent "<<"\t\t\t"<<" 8. Anscestor "<<"\t\t"<<" 12. Root "<<endl;
cout<<endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1:
{
cout<<" Enter Number to be inserted : ";
cin>>tmp;
b.insert(tmp);
break;
}
case 2:
{
cout<<" Enter data to be deleted : ";
cin>>tmp;
b.remove(tmp);
getch();
break;
}
case 3:
{
cout<<endl;
cout<<" Traversals "<<endl;
cout<<"----------"<<endl;
cout<<" Pre-Order Traversal "<<endl;
cout<<" -------------------"<<endl;
b.print_preorder();
cout<<endl;
cout<<" Post-Order Traversal "<<endl;
cout<<" --------------------"<<endl;
b.print_postorder();
cout<<endl;
cout<<" In-Order Traversal "<<endl;
cout<<" -------------------"<<endl;
b.print_inorder();
cout<<endl;
cout<<" Level-Order Traversal "<<endl;
cout<<" -------------------- "<<endl;
b.print_levelorder();
getch();
break;
}
case 4:
{
cout<<endl;
cout<<" The Parent Nodes Are: ";
getch();
break;
}
case 5:
{
cout<<endl;
cout<<" The Siblings Are: ";
getch();
break;
}
case 6:
{
cout<<" The Descendants Are: ";
getch();
break;
}
case 7:
{
cout<<" Leaf Node Are: ";
getch();
break;
}
case 8:
{
cout<<" The Node Anscestors Are: ";
getch();
break;
}
case 9:
{
cout<<" Indegree nodes: ";
getch();
break;
}
case 10:
{
cout<<" Outdegree nodes: ";
getch();
break;
}
case 11:
{
cout<<" Nodes in the tree: ";
getch();
break;
}
case 12:
{
cout<<" The Root of the Tree: ";
b.getroot();
getch();
break;
}
case 13:
{
cout<<" The Size of the tree is : ";
b.print_treesize();
getch();
break;}
case 0:
{
cout<<"\t\t\t Thanks for using my program ";
cout<<"\n\t\t\t Press Enter Again to Exit ";
getch();
return 0;
}
}
}while(ch != 0);
return 0;
}.H CODE
#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <queue>
using namespace std;
class BinaryTree
{
private:
struct node
{
struct node* left;
struct node* right;
struct node* root;
int data;
int contents;
};
node* root;
public:
BinaryTree();
~BinaryTree();
bool isEmpty() const { return root==NULL; }
void print_inorder();
void inorder(node*);
void print_preorder();
void preorder(node*);
void print_postorder();
void postorder(node*);
void print_tree(struct node *tree);
void print_level(struct node *tree, int spec_level, int cur_level);
void print_levelorder();
void insert(int);
void remove(int);
void leafs(node *current);
void print_leafs();
void nodeCount(node *count);
void anscestors(node *);
void getroot();
void Outdegree();
int treeSize(node *);
void print_treesize();
};
BinaryTree::BinaryTree()
{
root = NULL;
}
BinaryTree::~BinaryTree()
{
delete [] root;
}
// Smaller elements go left
// larger elements go right
void BinaryTree::insert(int d)
{
node* t = new node;
node* parent;
t->data = d;
t->left = NULL;
t->right = NULL;
t->root = NULL;
parent = NULL;
// is this a new tree?
if(isEmpty()) root = t;
else
{
//Note: ALL insertions are as leaf nodes
node* curr;
curr = root;
// Find the Node's parent
while(curr)
{
parent = curr;
if(t->data > curr->data) curr = curr->right;
else curr = curr->left;
}
if(t->data < parent->data)
parent->left = t;
else
parent->right = t;
}
}
void BinaryTree::remove(int d)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return;
}
node* curr;
node* parent;
curr = root;
while(curr != NULL)
{
if(curr->data == d)
{
found = true;
break;
}
else
{
parent = curr;
if(d>curr->data) curr = curr->right;
else curr = curr->left;
}
}
if(!found)
{
cout<<" Data not found! "<<endl;
return;
}
// 3 cases :
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children
// Node with single child
if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr)
{
parent->left = curr->right;
delete curr;
}
else
{
parent->right = curr->right;
delete curr;
}
}
else // left child present, no right child
{
if(parent->left == curr)
{
parent->left = curr->left;
delete curr;
}
else
{
parent->right = curr->left;
delete curr;
}
}
return;
}
//We're looking at a leaf node
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr) parent->left = NULL;
else parent->right = NULL;
delete curr;
return;
}
//Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
node* chkr;
chkr = curr->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
curr = chkr;
delete chkr;
curr->right = NULL;
}
else // right child has children
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element
if((curr->right)->left != NULL)
{
node* lcurr;
node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->data = lcurr->data;
delete lcurr;
lcurrp->left = NULL;
}
else
{
node* tmp;
tmp = curr->right;
curr->data = tmp->data;
curr->right = tmp->right;
delete tmp;
}
}
return;
}
}
void BinaryTree::print_inorder()
{
inorder(root);
}
void BinaryTree::inorder(node* p)
{
if(p != NULL)
{
if(p->left) inorder(p->left);
cout<<" "<<p->data<<" ";
if(p->right) inorder(p->right);
}
else return;
}
void BinaryTree::print_preorder()
{
preorder(root);
}
void BinaryTree::preorder(node* p)
{
if(p != NULL)
{
cout<<" "<<p->data<<" ";
if(p->left) preorder(p->left);
if(p->right) preorder(p->right);
}
else return;
}
void BinaryTree::print_postorder()
{
postorder(root);
}
void BinaryTree::postorder(node* p)
{
if(p != NULL)
{
if(p->left) postorder(p->left);
if(p->right) postorder(p->right);
cout<<" "<<p->data<<" ";
}
else return;
}
void BinaryTree::print_level(struct node *tree, int spec_level, int cur_level)
{
if(spec_level == cur_level)
cout<<" "<<tree->data<<" ";
else
{
if(tree->left) print_level(tree->left, spec_level, cur_level + 1);
if(tree->right) print_level(tree->right, spec_level, cur_level + 1);
}
}
void BinaryTree::print_tree(struct node *tree)
{
int i;
for(i = 0; i < 5; i++)
{
print_level(tree, i, 0);
}
}
void BinaryTree::print_levelorder()
{
print_tree(root);
}
void BinaryTree::nodeCount(node *count)
{
nodeCount(count->left);
count++;
nodeCount(count->right);
cout<<" "<<count->data<<" ";
}
void BinaryTree::leafs(node *current)
{
leafs(current->left);
leafs(current->right);
cout<<" "<<current->contents<<" ";
}
void BinaryTree::print_leafs()
{
leafs(root);
}
void BinaryTree::anscestors( node* l ) {
anscestors( l->left );
anscestors( l->right );
anscestors( l->root );
cout <<" "<<l->data <<" "<<endl;
}
void BinaryTree::getroot()
{
cout<<root->data;
}
void BinaryTree::Outdegree()
{
cout<<" 1 ";
}
int BinaryTree::treeSize(node *node)
{
if(node == NULL)
return 0;
else
return treeSize(node->left) + 1 + treeSize(node->right);
}
void BinaryTree::print_treesize()
{
treeSize(root);
}