Saturday, June 7, 2014

Binary Tree Traversal using Recursive and Non-Recursive Methods [Java]

This program takes user input into a binary tree and the traverses the tress displaying the values using recursive and non recursive functions (Non recursive function for Inorder traversal):

Suppose the user inputs (-999 is taken as an end marker for input):
14 15 4 9 7 18 3 5 16 4 20 17 9 14 5 -999

The output of the program using both methods is (for Inorder traversal):
3 4 4 5 5 7 9 9 14 14 15 16 17 18 20 
Java Code:

import java.util.Scanner;

class nodetype{
    public int info;
    public nodetype left;
    public nodetype right;
}

public class NonRecursiveInorderTreeTraversal {
    
    //General tree construction code
    static nodetype getnode(){
        return new nodetype();
    }
    
    static nodetype maketree(int x){
        nodetype p = getnode();
        p.info = x;
        p.left = null;
        p.right = null;
        return p;
    }
    
    static void setleft(nodetype p, int x){
        if(p==null)
            System.out.println("void insertion\n");
        else if(p.left != null)
            System.out.println("invalid insertion\n");
        else p.left = maketree(x);
    }
    
    static void setright(nodetype p, int x){
        if(p==null)
            System.out.println("void insertion\n");
        else if(p.right != null)
            System.out.println("invalid insertion\n");
        else
         p.right = maketree(x);
    }
    
    /* Traversal in preorder, inorder and postorder */
    static void pretrav(nodetype tree){
        if(tree!=null){
            System.out.print(tree.info+" ");
            pretrav(tree.left);
            pretrav(tree.right);
        }
    }
    
    static void intrav(nodetype tree){
        if(tree!=null){
            intrav(tree.left);
            System.out.print(tree.info+" ");
            intrav(tree.right);
        }
    }
    
    static void posttrav(nodetype tree){
        if(tree!=null){
            posttrav(tree.left);
            posttrav(tree.right);
            System.out.print(tree.info+" ");
        }
    }
    /***   ***/

    
     private static int MAXSTACK = 100;
    
     //Code for the stack used
     static class stack{
         int top;
         nodetype[] item = new nodetype[MAXSTACK];
        
        {
            top = 0;
            item = new nodetype[MAXSTACK];
        }
        
         void push(nodetype it){
            if(top<MAXSTACK)
            item[top++] = it;
            else
                System.out.println("Stack Overflow!");
        }
         nodetype pop(){
            if(top!=0)
                return item[--top];
            else
                System.out.println("Nothing to pop!");
            return null;
        }
         boolean empty(){
            if(top==0){
                return true;
            }
            return false;
        }
    }
    
    //Non Recursive traversal method (inorder) using stack
static void intrav2(nodetype tree){ stack s = new stack(); s.top = 0; nodetype p = tree; do{ /*                 travel down left branches as far as possible                 saving pointers to nodes passed             */ while(p!=null){ s.push(p); p = p.left; } /*end while*/ /*check if finished */ if(!s.empty()){ /* at this point the left subtree is empty */ p = s.pop(); System.out.print(p.info+" "); /*visit the root*/ p = p.right; /*traverse right subtree*/ } /*end if*/ }while(!s.empty() || p!= null); }/* end funtion */ public static void main(String[] args){ nodetype ptree; nodetype p = null, q; int number; System.out.println("Binary Tree Traversal\n\n"); System.out.println("Enter numbers :"); Scanner scan = new Scanner(System.in); number = scan.nextInt(); ptree = maketree(number); while((number=scan.nextInt())!=-999){ p = q = ptree; while(q!=null){ p=q; if(number<p.info) q = p.left; else if(number>=p.info) q = p.right; } if (number<p.info) setleft(p, number); else if(number>=p.info) setright(p, number); } System.out.println("\nUsing recursive function intrav: "); intrav(ptree); System.out.println("\nUsing non recursive function intrav2: "); intrav2(ptree); } }

No comments:

Post a Comment