Hi,I hope someone will help me on this,does anyone here knows algorithm BST infix to postfix,can you help me please.

I am not good in java and i am still getting know with this.

Thank you in advance.

Yes, many people here have done projects in that area.

Hoever, DaniWeb Member Rules (which you agreed to when you signed up) include:
"Do provide evidence of having done some work yourself if posting questions from school or work assignments"
http://www.daniweb.com/community/rules

Post what you have done so far and someone will help you from there.

Hi JamesCherill,..Thank you for the reply...This where i get stuck.,I have no idea yet how can i achieve BST infix to postfix,..I hope you can help me on this...I just want to know the algorithm so that i can have idea,.I am still newbie on java programming. Thank you in advance

public class BSTNode{

    private int item;
    private BSTNode left;
    private BSTNode right;


    public BSTNode (){}

    public BSTNode (int item){
        this.item = item;

    }

    public BSTNode(int item){
        this(item);
    }


    public void setRight(int item) {
        BSTNode temp = new BSTNode(item);
        this.right = temp;
    }

    public void setLeft(int item) {
        BSTNode temp = new BSTNode(item);
        this.left = temp;

    }

    public void setItem(int item){
        this.item = item;
    }


    public int getItem() {
        return item;
    }



    public BSTNode getLeft() {
        return left;
    }

    public BSTNode getRight() {
        return right;
    }

    public boolean isEmpty()
    {
        return root==null;
    }


    public void infix(int n){
         //here i am stuck,...


    }



    public static void main(String [] args){

        BSTNode root = new BSTNode(50);


    }


}

Edited 2 Years Ago by toring

You could start with Google. There are many sites with tutorials on the theory and implementation. You can't expect someone here to write a new one just for you!

Hi James,I understand i did not expect someone to write for me a code,i just want to know a little idea so that i can start writing my code...

I just googled
algorithm BST infix to postfix
and immediately got a whole load of tutorials and samples.

Start with those and come back here if you get stuck

Hi James, Maybe i am in the wrong forum to ask some help,,this is not for the beginners or beginners are not get much more help here, this is for an advance people like you...I think!

You are on the right place its just you expect the entire algorithm given at once, if you really want to learn how to do it, start by what you did and ask a specific question about the code where you are stucked, or why does your code not work/what kind of errors you get.

Maybe 90% of the people who get help here are beginners. But we do expect people to show some initiative and put in some work if they expect us to take time with them.

Hi James,

How do i print the data that i inserted ?..

public class BSTO {

    BSTO rightchild;
    BSTO leftchild;
    int data;
    BSTO root;



    public BSTO(){}

    public void Insert(int data){
        BSTO newnode = new BSTO();

        newnode.data = data;
        newnode.leftchild = null;
        newnode.rightchild = null;

        BSTO current = null;
        BSTO temp = null;

        if(root==null){
            root = newnode;
        }else{
             temp = root;
            while(temp!=null){

              current = temp;

                if(data<current.data)
                {
                    temp=temp.leftchild;
                    if(temp==null){
                        current.leftchild = newnode;
                        return;
                    }


                }
                else
                {
                    temp=temp.rightchild;
                    if(temp==null){
                        current.rightchild = newnode;
                        return;
                    }


                }

            }//End while

        }

    }



    public static void main(String []args){

        BSTO bsto = new BSTO();

        bsto.Insert(5);
        bsto.Insert(8);
        bsto.Insert(4);
        bsto.Insert(6);
        bsto.Insert(2);
        bsto.Insert(3);
        bsto.Insert(9);



    }

}

Edited 2 Years Ago by toring

You'll need to traverse the whole tree by following the leftchild and rightchild links. That requires a recursive solution - a quick Google for
BST traversal recursive
will give you a load of useful references.

Hi james,Is this correct?

public class BSTO {

    BSTO rightchild;
    BSTO leftchild;
    Character data;
    BSTO root;



    public BSTO(){}

    public void Insert(Character data){
        BSTO newnode = new BSTO();

        newnode.data = data;
        newnode.leftchild = null;
        newnode.rightchild = null;

        BSTO current = null;
        BSTO temp = null;

        if(root==null){
            root = newnode;
        }else{
             temp = root;
            while(temp!=null){

              current = temp;

                if(data<current.data)
                {
                    temp=temp.leftchild;
                    if(temp==null){
                        current.leftchild = newnode;
                        return;

                    }


                }
                else
                {
                    temp=temp.rightchild;
                    if(temp==null){
                        current.rightchild = newnode;
                        return;
                    }


                }

            }//End while

        }

    }

    private void postOrder(BSTO rot)
    {
        if(rot != null)
        {
            postOrder(rot.leftchild);
            postOrder(rot.rightchild);
            System.out.print(rot.data + " ");
        }
    }

    public static void main(String []args){

        BSTO bsto = new BSTO();

        bsto.Insert('5');
        bsto.Insert('*');
        bsto.Insert('2');
        bsto.Insert('/');
        bsto.Insert('6');



        bsto.postOrder(bsto.root);
    }

}

Hi james, Okay it prints now but is there something that i will do to output postfix?..by the way is that correct I use Character not char ?

"is there something that i will do to output postfix?" Google is your friend.

"is that correct I use Character not char?" In this case I can't see any reason for chosing one or the other. In any case, Java will automatically convert between them ("boxing" and "unboxing") as needed. So don't worry.

Hi james, I really could not find how to do it infix to postfix in BST

I don't know. I never studied computer science. But ata guess - no, it's not possible not to use a stack.

Edited 2 Years Ago by JamesCherrill

Hi james,Is it possible not to use stack?

What do you mean by that? The system stack or your own stack? You can convert infix to postfix using a lot of things. You should be able to write it using a BST without using your own stack if you wanted:

Step 1: Parse infix into BST recursively.
Step 2: Write BST in postfix notation.

You could also use your own stack to traverse the BST iteratively. You could also just use your own stack to do it iteratively. You could also just do it recursively without any extra data structure.

In all cases though, your either using the system stack or your own stack.

I am asking because i am confuse if we use the stack to produce postfix then the result of postfix is on the stack not on the tree...

Hi james,Do i need to create another method to convert the infix to postfix?..I am confuse on this..I thought postorder will give us the postfix result.

Edited 2 Years Ago by toring

Hi james why is it 20 will read only 2?

public class BSTO {

    BSTO rightchild;
    BSTO leftchild;
    char data,ndata;
    BSTO root;




    public BSTO(){}

    public void Insert(String n){
        BSTO newnode = new BSTO();
        char [] cc;
        cc = n.toCharArray();


            newnode.data = cc[0];
            newnode.leftchild = null;
            newnode.rightchild = null;

            BSTO current = null;
            BSTO temp = null;

            if (root == null) {
                root = newnode;
            } else {
                temp = root;
                while (temp != null) {

                    current = temp;

                    if (ndata < current.data) {
                        temp = temp.leftchild;
                        if (temp == null) {
                            current.leftchild = newnode;
                            return;

                        }


                    } else {
                        temp = temp.rightchild;
                        if (temp == null) {
                            current.rightchild = newnode;
                            return;
                        }


                    }

                }//End while

            }



    }




    private void postOrder(BSTO rot)
    {
        if(rot != null)
        {
            postOrder(rot.leftchild);
            postOrder(rot.rightchild);
            System.out.print(rot.data + " ");
        }
    }



    public static void main(String []args){

        BSTO bsto = new BSTO();

        bsto.Insert(new String("5"));
        bsto.Insert(new String("*"));
        bsto.Insert(new String("20"));






        bsto.postOrder(bsto.root);
    }

}

The output of postorder is: 2 * 5

Maybe because you store the data in a char, which only holds one character?
On lines 15-19 you carefully take just the first character from the String and ignore the rest.

Okay i fixed it but the output is: 02*5

can i ask during the insert method do in need to convert it to postfix so that in my method postorder the output will be correct ?...

Edited 2 Years Ago by toring

This is the code but the output is : 0 2 * 5

   public void Insert(String str){



        for(int i=0;i<str.length();i++){
            BSTO newnode = new BSTO();

            cc = str.toCharArray();


            newnode.data = cc[i];
            newnode.leftchild = null;
            newnode.rightchild = null;


             if (root == null) {
                 root = newnode;
             } else {
                 temp = root;
                 while (temp != null) {

                     current = temp;

                     if (cc[i] < current.data) {
                         temp = temp.leftchild;
                         if (temp == null) {
                             current.leftchild = newnode;
                             break;

                         }


                     } else {
                         temp = temp.rightchild;
                         if (temp == null) {
                             current.rightchild = newnode;
                             break;
                         }


                     }

                 }//End while

             }




        }//for loop


    }

I have no idea why you are inserting your strings as multiple nodes, one per character... But that's why your "20" becomes "0" and "2"

This article has been dead for over six months. Start a new discussion instead.