Binary Search Tree (Without Recursion) - DSTC using C Language (Source Code Implemented)

BINARY SEARCH TREE (Without Recursion)
Implemented using C Language  

 C Language Code:

---

BINTREE2.CPP

---

 // DSTC --- BINTREE2.CPP .... using BINTREE2.H
// Binary Trees Using NON Recursion .... 
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include "bintree2.h"

int main()
{
    node *nd=NULL;
    node *temp;
    int n=0;
    clrscr();
    while(n>=0)
    {
        printf("\n Enter Value:");
        scanf("%d", &n);
        if (n>=0)
            nd = addnode(nd,n) ;
    }

temp =nd ;
    printf("\n PreOrder NON Recursive:\n ") ;
    preOrderNonRecursive(temp) ;
    temp=nd ;
    inOrder(temp);
    printf("\n PostOrder :\n");
    temp=nd ;
    nodeprintPostOrder(temp);
    killnode(nd);
} 

---

BINTREE2.H

---

// DSTC -> BINTREE2.H // Binary Trees Using NON Recursion ....

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

typedef struct nodetype
{
    int info ;
    struct nodetype *left ;
    struct nodetype *right ;
}node;

#include "stacklst.h"

node * addnode(node *nd,int v)
{
    node *temp=nd , *par = NULL, *newn ;
    newn = (node *) malloc(sizeof(node));
    newn->info = v ;
    newn->left = newn->right = NULL;

    if(nd == NULL)
    {
        nd = newn ;
        return nd ;
    }
else
    {   while(temp != NULL)
    {
        if( v >= temp->info)
        {
            par = temp ;
            temp = temp->right ;

        }
        else
        {
            par = temp ;
            temp = temp->left ;
        }
    } // end while

if(v >= par->info)
    {
        par->right = newn ;
    }
    else
    {
        par->left= newn ;
    }

    }
    return nd ;

}

void killnode(node *nd)
{
    if (nd)
    {
        killnode(nd->left);
        killnode(nd->right);
        free(nd);
    }
}

// Pre Order Traversal in Binary Tree without RECURSION
void preOrderNonRecursive(node *nd)
{
    node *temp = nd ;
    stacklst *s = makestacklst() ;

    while(temp)
    {
        while(temp)
        {
            printf(" %d " , temp->info) ;
            if (temp->right != NULL)
                push(s , temp->right);
            temp = temp->left ;

        }
        if (!empty(s))
            temp = pop(s) ;
    }
}

void inOrder(node *nd)
{
    node *temp =nd ;
    stacklst  *s = makestacklst() ;

    do
    {
        while(temp)
        {
            push(s,temp) ;
            temp = temp ->left ;
        }

        while(!empty(s))
        {
            temp = pop(s) ;
            printf(" %d ", temp->info) ;
            if(temp->right != NULL)
            {
                temp = temp->right ;
                break ;
  }
            else
            {
                temp = NULL ;
            }
        }
    }while((temp !=NULL) || (!empty(s))) ;
}

void postOrderNonRecursive(node *nd)
{
      node *k=nd , *k1 ;
      stacklst  *s = makestacklst() ;
      do
      {
            while(k != NULL)
            {
                  push(s,k) ;
                  if(k->right != NULL)
                  {
                        k1 = k->right ;
                        k1->info  = -k1->info ;
                        push(s,k1);

                  }
                  k = k->left ;
            }
            while(s->top!=NULL)
            {
                  k = pop(s);
                  if (k->info >=0)
                        printf(" %d " , k->info);
                  else
                  {
                        k->info = -k->info ;
                        break ;
                  }
            }
      }while(s->top!=NULL) ;
}

---

STACKLST.H

---

 // DSTC - STACKLST.H .... Stacks using Linked Lised ...

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

typedef struct stacklistnode
{
    nodetype *info ;
    struct stacklistnode *next ;
}node1 ;

typedef struct stacklist
{
    node1 *top ;
}stacklst ;

stacklst *makestacklst()
{
    stacklst *t ;
    t = (stacklst *)malloc(sizeof(stacklst)) ;
    t->top = NULL ;
    return t;
}

node1 *makenode()
{
    node1 *t ;
    t = (node1 *)malloc(sizeof(node1)) ;
    return t ;
}

int empty(stacklst *s)
{
    if (s->top == NULL)
        return 1 ;
    else
        return 0 ;
}

void push(stacklst *s,nodetype *v)
{
    node1 *n ;
    n = makenode();
    n->info = v ;
    n->next = s->top ;
    s->top = n ;
}

nodetype *pop(stacklst *s)
{
    nodetype *v ;
    node1 *t;
    if (empty(s))
    {
        printf("\nStack Empty");
        return NULL;
    }

    v = s->top->info ;
    t = s->top ;
    s->top = t->next ;
    free(t) ;
    return (v) ;
}