Tuesday, February 6, 2018

Binary Tree creation with c++ using class and inorder traversal without recursion

//// Created by Laxmi Kadariya on 2/5/18.
//This is the source code to create binary tree with class in c++//#include "iostream"#include <stack>using namespace std;
struct node{

    int item;
    struct node *left;
    struct node *right;
};

class bst{

    private:
         struct node *root;

    public:


    struct node* insert_node(node *root,int item)
    {
      if(root == NULL) {
          root = new node;
          root->item = item;
          root->left = NULL;
          root->right = NULL;
      }

        else{

          if(root->item< item)
          {
            root->left =  insert_node(root->left,item);
          }
          else if(root->item >item)
          {
             root->right = insert_node(root->right,item);

          }
      }

        return root;

    }

    /*Method to print inorder traversal of a BST*/   
 void inorder(node *root)
    {
        stack<node*> stack;
        node *curr=root;
        while(!stack.empty() || curr!=NULL)
        {
            /*If current node is not NULL push the node in stack*/            
           if(curr!=NULL)
            {
                stack.push(curr);
                curr=curr->left;
            }
                /*If current node is empty or NULL pop it from the stack */           
           else           
            {
                curr=stack.top();
                stack.pop();
                cout<<curr->item<<" ";
                curr=curr->right;
            }
        }
    }





};



int main()
{
    bst tree;
    struct node *root = NULL;
    root = tree.insert_node(root,1);
    tree.insert_node(root,2);
    tree.insert_node(root,13);
    tree.insert_node(root,4);

    tree.inorder(root);

}

No comments:

Post a Comment