Tree Data Structure

// Mairaj.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;
class node
{
         
private:
          int val;
          node *right;
          node *left;
public:
          void setvalue(int x)
          {
                   val=x;

          }
          int getvalue()
          {
                   return val;
          }
          void setright(node *a)
          {
                   right=a;
          }
          node * getright()
          {
                   return right;
          }
    void setleft( node * b)
          {
                   left=b;
          }

          node * getleft()
          {
                   return left;

          }
          };


class Tree
{
private:
          node *root;
public:
          Tree(int y)
          {
                   node *temp=new node();
                   root=temp;
                   temp->setvalue(y);
                   temp->setright(NULL);
                   temp->setleft(NULL);
         
          }
          node * getroot()
          {
                   return root;
          }

void addnode(int c)
{
node * m=new node();
node *temp=root;
node *temp1=temp;
int a;

m->setvalue(c);
m->setright(NULL);
m->setleft(NULL);

do
{
temp=temp1;
if(temp->getvalue()>c)
{
temp1=temp->getleft();
a=0;
}
else
{
          temp1=temp->getright();
          a=1;
}
}
while(temp1);
if(a==0)
{temp->setleft(m);
}
else
{
          temp->setright(m);
}


}       



void shownode ()
{       
          node *temp=root;
          cout<<"Showing left childs data"<<endl;
          while(temp)
          {
                   cout<<temp->getvalue()<<endl;
                   temp=temp->getleft();

          }
          cout<<"Showing right childs data"<<endl;
          temp=root;
          while(temp)
          {
                   cout<<temp->getvalue()<<endl;
                   temp=temp->getright();
          }

}
void preorder(node* p)
{
    if(p != NULL)
    {
                   cout<<" "<<p->getvalue()<<" ";
                   if(p->getleft()!=NULL) preorder(p->getleft());
                   if(p->getright()!=NULL) preorder(p->getright());
    }
    else return;
}
void postorder(node* p)
{
    if(p != NULL)
    {
        if(p->getleft()) postorder(p->getleft());
        if(p->getright()) postorder(p->getright());
        cout<<" "<<p->getvalue()<<" ";
    }
    else return;
}
void inorder(node* p)
{
    if(p != NULL)
    {
        if(p->getleft()) inorder(p->getleft());
        cout<<" "<<p->getvalue()<<" ";
        if(p->getright()) inorder(p->getright());
    }
    else return;
}


node *search(int x)
{
          node *temp=root;
         
          node *add;
         
          while(temp!=NULL)
          {
                  
          if(temp->getvalue()==x)
          {        cout<<"Value Found"<<endl;
                   add=temp;
                   temp=NULL;
                  
          }
          else if(temp->getvalue()>x && temp->getleft()!=NULL)
          {
                   temp=temp->getleft();
          }
          else if(temp->getvalue()<x && temp->getright()!=NULL)
          {
                   temp=temp->getright();
          }
         
          else
          {        cout<<"value not found";
                   add=NULL;
                   temp=NULL;
                  
          }
          }

         
          return add;
}
void deletenode(int d)
{
                   //Locate the element
    bool found = false;
   
    node* curr;
    node* parent;
    curr = root;
    while(curr != NULL)
    {
                   if(curr->getvalue() == d)
         {
            found = true;
            break;
         }
         else
         {
             parent = curr;
                              if(d>curr->getvalue()) curr = curr->getright();
                              else curr = curr->getleft();
         }
    }
    if(!found)
                    {
        cout<<" Value 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->getleft() == NULL && curr->getright() != NULL)|| (curr->getleft() != NULL
                   && curr->getright() == NULL))
    {
                   if(curr->getleft() == NULL && curr->getright() != NULL)
       {
                      if(parent->getleft() == curr)
           {
                                parent->setleft(curr->getright());
             delete curr;
           }
           else
           {
                                parent->setright( curr->getright());
             delete curr;
           }
       }
       else // left child present, no right child
       {
                      if(parent->getleft() == curr)
           {
                                parent->setleft( curr->getleft());
             delete curr;
           }
           else
           {
                                parent->setright( curr->getleft());
             delete curr;
           }
       }
                   cout<<"Value Deleted"<<endl;     
     return;
    }

                    //We're looking at a leaf node
          if( curr->getleft() == NULL && curr->getright() == NULL)
    {
                   if(parent->getleft() == curr) parent->setleft( NULL);
                   else parent->setright(NULL);
                                       delete curr;
                                       cout<<"Value Deleted"<<endl;    
                                       return;
    }


    //Node with 2 children
    // replace node with smallest value in right subtree
          if (curr->getleft() != NULL && curr->getright() != NULL)
    {
        node* chkr;
                   chkr = curr->getright();
        if((chkr->getleft() == NULL) && (chkr->getright() == NULL))
        {
            curr = chkr;
            delete chkr;
            curr->setright(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->getright())->getleft() != NULL)
            {
                node* lcurr;
                node* lcurrp;
                lcurrp = curr->getright();
                lcurr = (curr->getright())->getleft();
                while(lcurr->getleft() != NULL)
                {
                   lcurrp = lcurr;
                   lcurr = lcurr->getleft();
                }
                                      curr->setvalue(  lcurr->getvalue());
                delete lcurr;
                lcurrp->setleft(NULL);
                             }
                             else
                             {
               node* tmp;
               tmp = curr->getright();
               curr->setvalue(tmp->getvalue());
                                curr->setright(tmp->getright());
               delete tmp;
                             }

        }
                                      cout<<"Value Deleted"<<endl;     
                                      return;
          }
                            

          }
};


int _tmain(int argc, _TCHAR* argv[])
{
                  

                   Tree i(10);
                   node *n=NULL;
                   node *r=i.getroot();
                   char ch;
          do
          {
                   cout<<"                                     MENU "<<endl;
                   cout<<"1.insert node"<<endl;
                  
                   cout<<"2.display "<<endl;
         
                   cout<<"3.search"<<endl;
                   cout<<"4.Preorder Traversal"<<endl;
                   cout<<"5.Postorder Traversal"<<endl;
                   cout<<"6.Inorder Traversal"<<endl;
                   cout<<"7.Delete Node"<<endl;
                   cout<<"8.exit"<<endl;
                   cout<<"Enter your choice ";
                   cin>>ch;
                   switch(ch)
                   {
                   case '1':
                            
                             i.addnode(5);
                             i.addnode(6);
                             i.addnode(7);
                             i.addnode(3);
                             i.addnode(1);
                             i.addnode(4);
                             i.addnode(12);
                             i.addnode(15);
                            
                             break;
                   case '2':
                                      i.shownode();
                             break;
                   case '3':
                             int srch;
                             cout<<"Enter value to search ";
                             cin>>srch;
                             i.search(srch);
                             break;
                   case '4':
                             i.preorder(r);
                            
                                      break;
                   case '5':
                             i.postorder(r);
                             break;
                   case '6':
                             i.inorder(r);
                             break;
                   case '7':
                             int value;
                             cout<<"Enter value to delete ";
                             cin>>value;
                             i.deletenode(value);
                             break;
                   case '8':
                             break;
                   default:
                             break;
                   }
          }
          while(ch<'8');
         
          return 0;
}





Comments

Post a Comment

Popular posts from this blog

Using Progress Bar In C#

Image
Using Progress Bar in C#: Progress Bar is very commonly used control in many applications to display the progress of task being performed. Progress Bar is displayed when copying files, deleting files or installing some software. How to use Progress Bar: ·          Start New Windows Form Application. ·          Go to Toolbox. ·          Select Progress Bar and Drag it to your Form. To make Progress Bar working you need to know some properties of Progress Bar Progress Bar.Maximum: Defines how long it should run Progress Bar.Step: Defines how much it should increase current position of Progress Bar. Progress Bar.Style: How should it look like? There is also a very basic method which is used to run Progress Bar properly. Progress Bar.PerformStep() Let’s see an example. In this example we will copy files and folders from one location to another and show the progress bar wh...
Read more

Check if ViewBag is null or doesn't exist

ASP.NET MVC uses  ViewBag to store some data from Controller and than accessed in View like you can save UserName in ViewBag who is logged in to your website and than display it in view. Sometimes you need to check if ViewBag exists or it is not null than execute your next piece of code. Let's take an example. Controller Code public ActionResult Index() { ViewBag . UserName = "John"; return View(); } View Code @if ( ViewBag . UserName ! = null ) { < label >@ViewBag.UserName</ label >;     } Here if ViewBag.UserName is not null than label will be rendered with username. If it is null the code will not execute. So you can easily check for a ViewBag Property and execute your code.
Read more

Jquery serer side datatables in asp.net

In this post we will learn how we can implement jquery   server side datatables in asp.net mvc application. We need to add datatables library to our page, we can add references of libray from datatables <a href="https://datatables.net/" target="_blank">website</a>. We need to create an html table on which we will apply datatable. <table class="table table-striped table-bordered table-hover table-checkable order-column dataTable" id="tblInventoryItems">   <thead>     <tr>       <th>Item Name</th>       <th>Item Price</th>       <th>Item Quantity</th>       <th></th>     </tr>   </thead>   <tbody></tbody> </table> Then we need the code which will apply the datatable to above html table. Below is the code to apply datatable $("yourtableid").DataTable({         "p...
Read more