I am looking for the non recursive code (C/C++ for Binary Search Tree, Please help?

Question

How to balance the binary search tree in C/C++? Please provide the necessary explanation also?

Answer 1

What is a Binary Search Tree
A graph without any loop is called a tree which has exactly n-1 connectors/edges for n nodes and always have a unique path between any two nodes. If in this type of arrangement each node has two connection to child nodes and one to the parent node then it is called binary tree and if in this type of binary tree each left subnode is less then then parent node and rigt subnode is greater then parent then it is called binary search tree.

What is Non-Recursive Implementation
Non-recursive implementation is the implementation where function doesn't call itself. The catch here is that you need a stack data-structure for traversal whereas in the case of recursion it is done by the compiler itself.

C++ implementation of Binary Search Tree

struct node
{
    int data;
    node *left;
    node *right;
};

typedef struct node *nodeptr;
class stack
{
    private:
        struct snode
        {
            nodeptr data;
            snode *next;
        };
        snode *top;
    public:
        stack()
        {
            top=NULL;
        }
        void push(nodeptr p)
        {
            snode *temp;
            temp = new snode;
            temp->data = p;
            temp->next = top;
            top=temp;
        }

        void pop()
        {
            if (top != NULL)
            {
            nodeptr t;
            snode *temp;
            temp = top;
            top=temp->next;
            delete temp;
            }
        }

        nodeptr topele()
        {
            if (top !=NULL)
                return top->data;
            else
                return NULL;
        }



        int isempty()
        {
        return ((top == NULL) ? 1 : 0);
        }

};


class bstree
{
    public:
        void insert(int,nodeptr &);
        void del(int,nodeptr &);
        int deletemin(nodeptr &);
        void find(int,nodeptr &);
        nodeptr findmin(nodeptr);
        nodeptr findmax(nodeptr);
        void copy(nodeptr &,nodeptr &);
        void makeempty(nodeptr &);
        nodeptr nodecopy(nodeptr &);
        void preorder(nodeptr);
        void inorder(nodeptr);
        void postorder(nodeptr);
        void preordernr(nodeptr);
        void inordernr(nodeptr);
        void postordernr(nodeptr);
        void leftchild(int,nodeptr &);
        void rightchild(int,nodeptr &);


};

void bstree::insert(int x,nodeptr &p)
{
    if (p==NULL)
    {
        p = new node;
        p->data=x;
        p->left=NULL;
        p->right=NULL;
    }
    else
    {
        if (x < p->data)
            insert(x,p->left);
        else if (x>p->data)
            insert(x,p->right);
        else
            cout<<"Element already Exits !";
    }
}

void bstree:: del(int x,nodeptr &p)
{
    nodeptr d;
    if (p==NULL)
        cout<<"Element not found ";
    else if (x < p->data)
        del(x,p->left);
    else if (x > p->data)
        del(x,p->right);
    else if ((p->left == NULL) && (p->right ==NULL))
    {
        d=p;
        free(d);
        p=NULL;
    }
     else if (p->left == NULL)
    {
        d=p;
        free(d);
        p=p->right;
    }
    else if (p->right ==NULL)
    {
        d=p;
        p=p->left;
        free(d);
    }
    else
    p->data=deletemin(p->right);
}

int bstree::deletemin(nodeptr &p)
{
    int c;
    if (p->left == NULL)
    {
        c=p->data;
        p=p->right;
        return c;
    }
    else
        c=deletemin(p->left);
        return c;
}

void bstree::copy(nodeptr &p,nodeptr &p1)
{
    makeempty(p1);
    p1=nodecopy(p);
}

void bstree::makeempty(nodeptr &p)
{
    nodeptr d;
    if (p!=NULL)
    {
        makeempty(p->left);
        makeempty(p->right);
        d=p;
        free(d);
        p=NULL;
    }
}

nodeptr bstree::nodecopy(nodeptr &p)
{
    nodeptr temp;
    if (p == NULL)
        return p;
    else
    {
        temp = new node;
        temp->data=p->data;
        temp->left = nodecopy(p->left);
        temp->right = nodecopy(p->right);
        return temp;
    }
}


nodeptr bstree::findmin(nodeptr p)
{
    if (p==NULL)
    {
        cout<<"Tree is empty !";
        return p;
    }
    else
    {
        while (p->left !=NULL)
            p=p->left;
        return p;
    }
}



nodeptr bstree::findmax(nodeptr p)
{
    if (p==NULL)
    {
        cout<<"Tree is empty !";
        return p;
    }
    else
    {
        while (p->right !=NULL)
            p=p->right;
        return p;
    }
}

void bstree::find(int x,nodeptr &p)
{
    if (p==NULL)
        cout<<"Element not found  !";
    else
    {
        if (x <p->data)
            find(x,p->left);
        else if ( x> p->data)
            find(x,p->right);
        else
            cout<<"Element Found !";
    }
}

void bstree::preorder(nodeptr p)
{
    if (p!=NULL)
    {
        cout<<p->data<<"-->";
        preorder(p->left);
        preorder(p->right);
    }
}
void bstree::inorder(nodeptr p)
{
    if (p!=NULL)
    {
        inorder(p->left);
        cout<<p->data<<"-->";
        inorder(p->right);
    }
}

void bstree::postorder(nodeptr p)
{
    if (p!=NULL)
    {
        postorder(p->left);
        postorder(p->right);
        cout<<p->data<<"-->";
    }
}



void bstree::preordernr(nodeptr p)
{
    stack s;
    while (1)
    {
    if  (p != NULL)
    {
        cout<<p->data<<"-->";
        s.push(p);
        p=p->left;
    }
    else
    if (s.isempty())
    {
        cout<<"Stack is empty";
        return;
    }
    else
    {
        nodeptr t;
        t=s.topele();
        p=t->right;
        s.pop();
    }
    }
}


void bstree::inordernr(nodeptr p)
{
    stack s;
    while (1)
    {
    if  (p != NULL)
    {
        s.push(p);
        p=p->left;
    }
    else
    {
    if (s.isempty())
    {
        cout<<"Stack is empty";
        return;
    }
    else
    {
        p=s.topele();
        cout<<p->data<<"-->";
    }
    s.pop();
    p=p->right;
    }
    }
}


void bstree::postordernr(nodeptr p)
{
    stack s;
    while (1)
    {
    if  (p != NULL)
    {
        s.push(p);
        p=p->left;
    }
    else
    {
        if (s.isempty())
        {
            cout<<"Stack is empty";
            return;
        }
        else
        if (s.topele()->right == NULL)
        {
            p=s.topele();
            s.pop();
            cout<<p->data<<"-->";
            if (p==s.topele()->right)
            {
                cout<<s.topele()->data<<"-->";
                s.pop();
            }
        }
        if (!s.isempty())
            p=s.topele()->right;
        else
            p=NULL;
    }
    }
}

void bstree::leftchild(int q,nodeptr &p)
{
    if (p==NULL)
        cout<<"The node does not exists ";

    else
    if (q < p->data )
        leftchild(q,p->left);
    else
    if (q > p->data)
        leftchild(q,p->right);
    else
    if (q == p->data)
    {
        if (p->left != NULL)
            cout<<"Left child of "<<q<<"is "<<p->left->data;
        else
            cout<<"No Left child !";
    }
}

void bstree::rightchild(int q,nodeptr &p)
{
    if (p==NULL)
        cout<<"The node does not exists ";
    else
    if (q < p->data )
        rightchild(q,p->left);
    else
    if (q > p->data)
        rightchild(q,p->right);
    else
    if (q == p->data)
    {
        if (p->right != NULL)
            cout<<"Right child of "<<q<<"is "<<p->right->data;
        else
            cout<<"No Right Child !";
    }
}

Answer 2

I got your question.You can take stack data structure for traversal BST.It will solve your problem means you can implement BST with non recursion code.

Answer 3

#include <fstream> 
#include <iostream>
#include <cstdlib>
#include <string>
#include <conio.h>
using namespace std;

struct node
{
 char* key;
    node* left;
    node* right;

};

class btree
{
private:
    node* root;
 void inordertraverse(node*);
 void destroy_tree(node*);
 node* find(char* ch);
public:
    btree();
 ~btree();
    bool isEmpty() const { return root==NULL; }
    void print_inorder();
    void search(char* ch);
    void insert(char* ch);
    void remove(char* dkey);
};

// constructor
btree::btree()
{
  root = NULL;
}

btree::~btree()
{
  destroy_tree(root);
}

void btree::destroy_tree(node* p)
{
 if (p != NULL)
 {
  destroy_tree(p->left);
  destroy_tree(p->right);
  delete p;
 }
}

void btree::search(char * ch)
{
 node* curr;
 if (root == NULL)  {
  cout<<" This Tree is empty! "<<endl;
  return;
 }
 curr = find(ch);
 if (curr != NULL)
  cout << ch  << " " << "Found!\n" << endl;
 else
  cout << ch  << " " << "Not found!\n" << endl;
}

node* btree::find(char * ch)
{
 node* curr = root;
    while( curr)
    {
        if(!strcmp(ch, curr->key))
        {
            return curr;
        }
        else if(strcmp(ch, curr->key)>0)
            curr = curr->right;
        else if(strcmp(ch, curr->key)<0)
            curr = curr->left;
    }
 return NULL;
}

void btree::insert(char * ch)
{
 node *temp = new node;
 temp->key = ch;
 temp->left = NULL;
 temp->right = NULL;
 if(root==NULL)
  root = temp;
 else
 {
  // find the correct location for the new node
  // and insert it
  bool inserted = false;
  node *locn = root;
  while( !inserted)
  {
   if(locn->key > temp->key)
   {
    if(locn->left == NULL)
    {
     locn->left = temp;
     inserted = true;
    }
    else
     locn = locn->left;
   }
   else
   { 
    if(locn->right == NULL)
    {
     locn->right = temp;
     inserted = true;
    }
    else
     locn = locn->right;
   }
  }
 }
}
void btree::remove(char* data)
{
 node *temp = root;
 node *prev = root;
 while (1)
 {
  if(temp == NULL)
   return;
  if(strcmp(temp->key , data) == 0)
  {
   bool left = false;
   if(prev->left == temp)
    left = true;
   if(temp->left == NULL && left)
   { 
    prev->left = temp->right;
    delete temp;
    return;
   }
   if(temp->right == NULL && left)
   {
    prev->left = temp->left;
    delete temp;
    return;
   }
   if(temp->left == NULL && left == false)
   {
    prev->right = temp->right;
    delete temp;
    return;
   }
   if(temp->right == NULL && left == false)
   {
    prev->right = temp->left;
    delete temp;
    return;
   }
   while(temp->left != NULL && temp->right != NULL)
   {
    temp->key = temp->right->key;
    prev = temp;
    temp = temp->right;
   }
   if(temp->right == NULL)
    prev->right = temp->left;
   if(temp->left == NULL)
    prev->right = temp->right;
   delete temp;
   return;
  }
  prev = temp;
  if(strcmp(temp->key,data) < 0)
   temp = temp->right;
  else
   temp = temp->left;
 }
}

void btree::print_inorder()
{
 if (root != NULL)
  inordertraverse(root);
 else
  cout<<" This Tree is empty! "<<endl;
}

void btree::inordertraverse(node* p)
{
    if (p != NULL)
    {
  inordertraverse(p->left);
        cout <<" President [\""<<p->key <<"\"]=" << endl;
        inordertraverse(p->right);
    }
    else return;
}


int main()
{
 btree prez;
    string temp, ftarget, dtarget;
    int ch = 0;
    string line;
    string a_1;
    ifstream myfile ("a.dat");
    if (myfile.is_open())
    {
        while(myfile.good())
        {
            getline (myfile,a_1);
            cout<<line<<endl;
        }
        myfile.close();
    }
    else
        cout<<"Unable to open";


    return 0;
}

Answer 4

#include<stdlib.h>
#include<stdio.h>

struct bin_tree {
int data;
struct bin_tree * right, * left;
};
typedef struct bin_tree node;

void insert(node ** tree, int val)
{
    node *temp = NULL;
    if(!(*tree))
    {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return;
    }

    if(val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    }
    else if(val > (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }

}

void print_preorder(node * tree)
{
    if (tree)
    {
        printf("%d\n",tree->data);
        print_preorder(tree->left);
        print_preorder(tree->right);
    }

}

void print_inorder(node * tree)
{
    if (tree)
    {
        print_inorder(tree->left);
        printf("%d\n",tree->data);
        print_inorder(tree->right);
    }
}

void print_postorder(node * tree)
{
    if (tree)
    {
        print_postorder(tree->left);
        print_postorder(tree->right);
        printf("%d\n",tree->data);
    }
}

void deltree(node * tree)
{
    if (tree)
    {
        deltree(tree->left);
        deltree(tree->right);
        free(tree);
    }
}

node* search(node ** tree, int val)
{
    if(!(*tree))
    {
        return NULL;
    }

    if(val < (*tree)->data)
    {
        search(&((*tree)->left), val);
    }
    else if(val > (*tree)->data)
    {
        search(&((*tree)->right), val);
    }
    else if(val == (*tree)->data)
    {
        return *tree;
    }
}

void main()
{
    node *root;
    node *tmp;
    //int i;

    root = NULL;
    /* Inserting nodes into tree */
    insert(&root, 9);
    insert(&root, 4);
    insert(&root, 15);
    insert(&root, 6);
    insert(&root, 12);
    insert(&root, 17);
    insert(&root, 2);

    /* Printing nodes of tree */
    printf("Pre Order Display\n");
    print_preorder(root);

    printf("In Order Display\n");
    print_inorder(root);

    printf("Post Order Display\n");
    print_postorder(root);

    /* Search node into tree */
    tmp = search(&root, 4);
    if (tmp)
    {
        printf("Searched node=%d\n", tmp->data);
    }
    else
    {
        printf("Data Not found in tree.\n");
    }

    /* Deleting all nodes of tree */
    deltree(root);
}

Output of Program:

$ ./a.out
Pre Order Display
9
4
2
6
15
12
17
In Order Display
2
4
6
9
12
15
17
Post Order Display
2
6
4
12
17
15
9
Searched node=4