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);
}

Edited 5 Years Ago by Narue: Added code tags

This article has been dead for over six months. Start a new discussion instead.