How does one implement a method in Binary Tree in returning the next node visited after variable?

2
votes

enter image description here

Preorder: / * + a b – c d + e f
Inorder: a + b * c – d / e + f
Postorder: a b + c d - * e f + /

Say we have this tree. I already got the code for printing out the orders; Preorder, Inorder and Postorder. Now whats left is the problem, the user is asked to input Preorder next to what character?, lets say the user entered the letter a, so the output should be

Preorder next to what character?: a
Preordernext(a) = b

and so on to Inorder and Postorder, now the problem is i cant seem to locate the next node from a specific node.

System.out.print("Preorder next of what character: ");
char q = scn.next().charAt(0);
System.out.print("PreorderNext("+q+")| ");
binaryTree.searchPostOrder(q);

So far this is what i came up with and I received no result aside from blank...

public void searchPostOrder(char kwanix) {
        searchPostorder(root, kwanix);
    }
    private char searchPostorder(Node node, char kwanix) {
        if (node.getData() == kwanix) {
            if (node.getLeft() != null) {
                if (node.getLeft().equals(kwanix)) {
                    kwanix = node.getData();
                }
            }
            if (node.getRight() != null) {
                if (node.getRight().equals(kwanix)) {
                    kwanix = node.getData();
                }
            }
        }
        return kwanix;
    }

This is the result after running the program

Post Order| d c b a 
Pre order| a c d b 
In order| c d a b 

Preorder next of what character: a
PreorderNext(a)|
2
javabinary-tree

2 Answers

3
votes

One (simple) solution:

You figured that your tree "walk" leads to different results.

Preorder: / * + a b – c d + e f
Inorder: a + b * c – d / e + f
Postorder: a b + c d - * e f + /

Note that this output contains all your nodes, just in different order. And look: in the sequence for the pre order row ... b comes right after a!

In other words: one simple solution is:

  • you pick the order strategy the user wants
  • you walk your tree in that order
  • when you find a, you continue to the next node (that is a leaf), and that is what you return as result
2
votes

My approach will be :

  1. I will move through all nodes and store value of only those nodes containing characters and not the operators. Example

    Preorder: / * + a b – c d + e f

    myArray => a b c d e f

My array will contain only characters : {a , b , c, d, e , f}.

  1. Then I will start a loop through index 0 to length of array.length-1 if encounter userSymbol then

Print [index+1]

else

Print empty.