Binary Search Tree Deletation

Discussion in 'Mac Programming' started by HINA ELLAHI, Dec 26, 2007.

  1. HINA ELLAHI macrumors newbie

    Joined:
    Dec 26, 2007
    Location:
    in pakistan
    #1
    hi its hina.actually there are some errors in deletation function while compling it plz help me and remove these errors.thanx ;)
    here is the complete code

    #include <constream.h>
    #include<iostream.h>
    #include<conio.h>

    class Node
    {
    private:
    int data;
    Node *left;
    Node *right;
    public:
    Node(int d=0)
    {
    data = d;
    left = NULL;
    right= NULL;
    }
    void setData(int d)
    {
    data = d;
    }
    int getData()
    {
    return data;
    }
    void setLeft(Node *l)
    {
    left = l;
    }
    Node *& getLeft()
    {
    return left;
    }
    void setRight(Node *r)
    {
    right = r;
    }
    Node *& getRight()
    {
    return right;
    }
    };

    class BinTree
    {
    private:

    Node * root;
    public:


    BinTree()
    {
    root = NULL;
    }
    Node *& getRoot()
    {
    return root;
    }
    void DeleteNode(struct node * & node);
    void insert(Node *&r,int d)
    {
    if(r == NULL)
    {
    Node * p = new Node(d);
    r = p;
    }
    else if(r->getData()>d)
    {
    insert(r->getLeft(),d);
    }
    else
    {
    insert(r->getRight(),d);
    }
    }
    void inOrderDisplay(Node *& r)
    {
    if(r != NULL)
    {
    inOrderDisplay(r->getLeft());
    cout<<r->getData()<<" ";
    inOrderDisplay(r->getRight());
    }
    }
    void postOrderDisplay(Node *& r)
    {
    if(r != NULL)
    {
    postOrderDisplay(r->getLeft());
    postOrderDisplay(r->getRight());
    cout<<r->getData()<<" ";
    }
    }
    void preOrderDisplay(Node *& r)
    {
    if(r != NULL)
    {
    cout<<r->getData()<<" ";
    preOrderDisplay(r->getLeft());
    preOrderDisplay(r->getRight());
    }
    }
    /*void del(Node *&r)
    {
    if(r->getLeft()==NULL&&r->getRight()==NULL)
    cout<<"LEAF DELETED";

    } ?*/
    };
    void DeleteNode(Node *&r)
    {
    if (r->getLeft()==NULL)
    {
    Node *temp=r;
    r=r->getRight();
    delete temp;
    }
    else if (r->getRight()==NULL)
    {
    Node *temp=r;
    r=r->getLeft();
    delete temp;
    }
    else
    {
    // In-order predecessor (rightmost child of left subtree)
    // Node has two children - get max of left subtree
    Node **temp = &r->getLeft();
    // get left node of the original node

    // find the rightmost child of the subtree of the left node
    while ((*temp)->getRight()!=NULL)
    {
    temp=&(*temp)->getRight();
    }

    // copy the value from the in-order predecessor to the original node
    r->setData()=(*temp)->getData();

    // then delete the predecessor
    DeleteNode(*temp);
    }
    void main()
    {
    clrscr();
    BinTree bst;
    bst.insert(bst.getRoot(),49);
    bst.insert(bst.getRoot(),66);
    bst.insert(bst.getRoot(),28);
    bst.insert(bst.getRoot(),13);
    bst.insert(bst.getRoot(),35);
    bst.insert(bst.getRoot(),62);
    bst.insert(bst.getRoot(),80);
    cout<<"\n\nPost Order Traversel"<<endl;
    bst.postOrderDisplay(bst.getRoot());
    cout<<"\n\nIn Order Traversel"<<endl;
    bst.inOrderDisplay(bst.getRoot());
    cout<<"\n\nPre Order Traversel"<<endl;
    bst.preOrderDisplay(bst.getRoot());
    cout<<endl<<endl;
    //del( );
    //del(bst.getRoot(),80);
    getch();

    }
     
  2. ChrisBrightwell macrumors 68020

    ChrisBrightwell

    Joined:
    Apr 5, 2004
    Location:
    Huntsville, AL
    #2
    Two suggestions:

    1. Post the exact error(s) you're getting
    2. Wrap your code in code and /code tags.
     

Share This Page