for Robot Artificial Inteligence

26. Binary Search Trees

19 Jun 2020 | Algorithm

Binary Search Tree

#include <iostream>

using namespace std;
class Node
{
public:
    int data;
    Node* rchild;
    Node* lchild;

};
class BST
{
public:
    BST(){root=nullptr;}
    ~BST(){}
    void Insert(int key);
    void Inorder(){ Inorder(root);}
    void Inorder(Node* p);
    Node* Search(int key);
private:
    Node* root;
};
Node* BST::Search(int key)
{
    Node* p = root;
    while(p!= nullptr)
    {
        if(key == p->data)
        {
            return p;
        }
        else if(key<p->data)
        {
            p=p->lchild;
        }
        else
        {
            p=p->rchild;
        }

    }
    return nullptr;

}
void BST::Inorder(Node* p)
{
    if(p!=nullptr)
    {
        Inorder(p->lchild);
        cout<< p->data << " ";
        Inorder(p->rchild);
    }
}
void BST::Insert(int key)
{
    Node* p = root;
    Node* t;
    Node* r;

    if(root==nullptr)
    {
        t = new Node;
        t->data = key;
        t->lchild =nullptr;
        t->rchild =nullptr;
        root = t;
        return;
    }
    while(p!=nullptr)
    {
        r = p; // lastest pointer point to last indicated point
        if(key<p->data)
        {
            p = p->lchild;
        }
        else if(key > p->data)
        {
            p = p->rchild;
        }
    }

    t = new Node;
    t->data = key;
    t->lchild =nullptr;
    t->rchild =nullptr;
    if(key<r->data)
        r->lchild = t;
    if(key>r->data)
        r->rchild = t;
}

int main()
{
    BST bst;
    bst.Insert(10);
    bst.Insert(5);
    bst.Insert(20);
    bst.Insert(8);
    bst.Insert(30);

    //Inorder Traversal
    bst.Inorder();
    cout<<endl;

    // Search
    Node* Search_result;
    Search_result = bst.Search(5);
    if(Search_result!=nullptr)
    {
        cout << Search_result->data;
    }
    else
    {
        cout << "not found";
    }
    return 0;
}

Recursive Inset and Delete on BST

#include <iostream>

using namespace std;
class Node
{
public:
    int data;
    Node* rchild;
    Node* lchild;

};
class BST
{
public:
    BST(){root=nullptr;}
    ~BST(){}
    void Insert(int key);
    void Inorder(){ Inorder(root);}
    void Inorder(Node* p);
    Node* Search(int key);
    Node* preorder(){ preorder(root);}
    Node* preorder(Node* p);
    Node* Delete(Node* p,int key);
    Node* getRoot();
    int height(Node* p);
    Node* Insucc(Node* p);
private:
    Node* root;
};
int BST::height(Node* p)
{
    int x;
    int y;
    if(p==nullptr)
        return 0;
    x = height(p->lchild);
    y = height(p->rchild);
    return x>y?x+1:y+1;
}
Node* BST::getRoot()
{
    return root;
}
Node* BST::preorder(Node* p)
{
    while(p && p->rchild!=nullptr)
    {
        p=p->rchild;
    }
    cout<<" InPre : "<< p->data<<endl;
    return p;
}
Node* BST::Search(int key)
{
    Node* p = root;
    while(p!= nullptr)
    {
        if(key == p->data)
        {
            return p;
        }
        else if(key<p->data)
        {
            p=p->lchild;
        }
        else
        {
            p=p->rchild;
        }

    }
    return nullptr;

}
void BST::Inorder(Node* p)
{
    if(p!=nullptr)
    {
        Inorder(p->lchild);
        cout<< p->data << " ";
        Inorder(p->rchild);
    }
}
void BST::Insert(int key)
{
    Node* p = root;
    Node* t;
    Node* r;

    if(root==nullptr)
    {
        t = new Node;
        t->data = key;
        t->lchild =nullptr;
        t->rchild =nullptr;
        root = t;
        return;
    }
    while(p!=nullptr)
    {
        r = p; // lastest pointer point to last indicated point
        if(key<p->data)
        {
            p = p->lchild;
        }
        else if(key > p->data)
        {
            p = p->rchild;
        }
    }

    t = new Node;
    t->data = key;
    t->lchild =nullptr;
    t->rchild =nullptr;
    if(key<r->data)
        r->lchild = t;
    if(key>r->data)
        r->rchild = t;
}
Node* BST::Delete(Node* p,int key)
{
    Node* q;
    if(p==nullptr)
    {
        return nullptr;
    }

    if(p->lchild==nullptr&&p->rchild==nullptr)
    {
        if(p==root)
        {
            root=nullptr;
        }
        delete p;
        return nullptr;
    }
    if(key<p->data)
    {
        p->lchild = Delete(p->lchild,key);
    }
    else if(key>p->data)
    {
        p->rchild = Delete(p->rchild,key);
    }
    else
    {
        if(height(p->lchild)>height(p->rchild))
        {
            q = preorder(p->lchild);
            p->data = q->data;
            p->lchild = Delete(p->lchild, q->data);
        }
        else
        {
            q = Insucc(p->rchild);
            p->data = q->data;
            p->rchild = Delete(p->rchild, q->data);
        }
    }
    return p;
}
Node* BST::Insucc(Node *p) {
    while (p && p->lchild != nullptr){
        p = p->lchild;
    }
    cout<< "InSucc: "<<p->data<<endl;
    return p;
}
int main()
{
    BST bst;
    bst.Insert(10);
    bst.Insert(5);
    bst.Insert(20);
    bst.Insert(8);
    bst.Insert(30);

    //Inorder Traversal
    bst.Inorder();
    cout<<endl;

    // Preoder
    bst.preorder();
    cout<<endl;


    // Search
    Node* Search_result;
    Search_result = bst.Search(5);
    if(Search_result!=nullptr)
    {
        cout << Search_result->data<<endl;;
    }
    else
    {
        cout << "not found";
    }
    // Delete
    bst.Delete(bst.getRoot(),20);
    bst.Inorder();
    cout<<endl;
    return 0;
}

Generating BST from Preorder.

#include <iostream>
#include <stack>

using namespace std;
class Node
{
public:
    int data;
    Node* rchild;
    Node* lchild;

};
class BST
{
public:
    BST(){root=nullptr;}
    ~BST(){}
    void Insert(int key);
    void Inorder(){ Inorder(root);}
    void Inorder(Node* p);
    Node* Search(int key);
    Node* preorder(){ preorder(root);}
    Node* preorder(Node* p);
    Node* Delete(Node* p,int key);
    Node* getRoot();
    int height(Node* p);
    Node* Insucc(Node* p);
    void createFromPreorder(int pre[], int size_);
private:
    Node* root;
};
void BST::createFromPreorder(int pre[], int size_)
{
    //Create root node
    int i = 0;
    root = new Node;
    root->data = pre[i++];
    root->lchild = nullptr;
    root->rchild = nullptr;

    // iteratives steps
    Node* t;
    Node* p = root;
    stack <Node*> stk;

    while(i<size_)
    {
        //left child case
        if(pre[i]<p->data)
        {
            t = new Node;
            t->data = pre[i++];
            t->lchild =nullptr;
            t->rchild =nullptr;
            p->lchild =t;
            stk.push(p);
            p = t;
        }
        else
        {
            //Right child case
            if(pre[i]>p->data && pre[i]<stk.empty()?32767:stk.top()->data)
            {
                t = new Node;
                t->data = pre[i++];
                t->lchild = nullptr;
                t->rchild = nullptr;
                p->rchild = t;
                p = t;
            }
            else
            {
                p = stk.top();
                stk.pop();
            }

        }
    }

}
int BST::height(Node* p)
{
    int x;
    int y;
    if(p==nullptr)
        return 0;
    x = height(p->lchild);
    y = height(p->rchild);
    return x>y?x+1:y+1;
}
Node* BST::getRoot()
{
    return root;
}
Node* BST::preorder(Node* p)
{
    while(p && p->rchild!=nullptr)
    {
        p=p->rchild;
    }
    cout<<" InPre : "<< p->data<<endl;
    return p;
}
Node* BST::Search(int key)
{
    Node* p = root;
    while(p!= nullptr)
    {
        if(key == p->data)
        {
            return p;
        }
        else if(key<p->data)
        {
            p=p->lchild;
        }
        else
        {
            p=p->rchild;
        }

    }
    return nullptr;

}
void BST::Inorder(Node* p)
{
    if(p!=nullptr)
    {
        Inorder(p->lchild);
        cout<< p->data << " ";
        Inorder(p->rchild);
    }
}
void BST::Insert(int key)
{
    Node* p = root;
    Node* t;
    Node* r;

    if(root==nullptr)
    {
        t = new Node;
        t->data = key;
        t->lchild =nullptr;
        t->rchild =nullptr;
        root = t;
        return;
    }
    while(p!=nullptr)
    {
        r = p; // lastest pointer point to last indicated point
        if(key<p->data)
        {
            p = p->lchild;
        }
        else if(key > p->data)
        {
            p = p->rchild;
        }
    }

    t = new Node;
    t->data = key;
    t->lchild =nullptr;
    t->rchild =nullptr;
    if(key<r->data)
        r->lchild = t;
    if(key>r->data)
        r->rchild = t;
}
Node* BST::Delete(Node* p,int key)
{
    Node* q;
    if(p==nullptr)
    {
        return nullptr;
    }

    if(p->lchild==nullptr&&p->rchild==nullptr)
    {
        if(p==root)
        {
            root=nullptr;
        }
        delete p;
        return nullptr;
    }
    if(key<p->data)
    {
        p->lchild = Delete(p->lchild,key);
    }
    else if(key>p->data)
    {
        p->rchild = Delete(p->rchild,key);
    }
    else
    {
        if(height(p->lchild)>height(p->rchild))
        {
            q = preorder(p->lchild);
            p->data = q->data;
            p->lchild = Delete(p->lchild, q->data);
        }
        else
        {
            q = Insucc(p->rchild);
            p->data = q->data;
            p->rchild = Delete(p->rchild, q->data);
        }
    }
    return p;
}
Node* BST::Insucc(Node *p) {
    while (p && p->lchild != nullptr){
        p = p->lchild;
    }
    cout<< "InSucc: "<<p->data<<endl;
    return p;
}
int main()
{
    BST bst;
    bst.Insert(10);
    bst.Insert(5);
    bst.Insert(20);
    bst.Insert(8);
    bst.Insert(30);

    //Inorder Traversal
    bst.Inorder();
    cout<<endl;

    // Preoder
    bst.preorder();
    cout<<endl;


    // Search
    Node* Search_result;
    Search_result = bst.Search(5);
    if(Search_result!=nullptr)
    {
        cout << Search_result->data<<endl;;
    }
    else
    {
        cout << "not found";
    }
    // Delete
    bst.Delete(bst.getRoot(),20);
    bst.Inorder();
    cout<<endl;

    // BST from Preorder Traversal
    cout << "BST from Preorder: " << flush;
    int pre[] = {30, 20, 10, 15, 25, 40, 50, 45};
    int n = sizeof(pre)/sizeof(pre[0]);

    BST b;
    b.createFromPreorder(pre,n);
    b.Inorder();
    return 0;
}

Quiz

Comments