binary tree traversal

1
votes

i have made an binary tree, and im trying to make an postorder traversal. I have already made an preorder traversal - which i though was what i needed. But after googling traversal i found out that it was postorder i need. My thoughts are on the traversal that first the left comes out, then the right and then the root(it is postorder right? :) ). I have tried to implement it, but it looks a bit odd the out come

public static <E> String postorder(BinaryTree<E> t, Position<E> v){
    String tree = "";
    if(t.hasLeft(v)){
        tree += postorder(t, t.left(v));
    }
    tree += v.element()  +", ";
    if(t.hasRight(v)){
        tree += postorder(t, t.right(v));
    }
    return tree;
}

My tree is:

            45
           /   \
          22    77
         /  \      \
        11   30     90
         \    /     /
         15  25    88

My result should be after my knowledge 15,11,25,30,22,88,90,77,45 But it is 11,15,22,25,30,45,77,88,90

Can anyone see what im doing wrong - i have tried so many things. Nothing works.

2
javabinary-tree

2 Answers

2
votes

You're calling preorder from within the implementation of postorder.

Update: now it looks like you're doing an in-order traversal but calling it postorder.

Move this line:

tree += v.element()  +", ";

to the end (right before returning).

0
votes
void preOrder(BSTNode *root){
    while(root != NULL){
       cout<<root->data<<endl;
       preOrder(root->left);
       preOrder(root->right);
    }
}

void postOrder(BSTNode *root){
    while(root != NULL){
       preOrder(root->left);
       preOrder(root->right);
       cout<<root->data<<endl;
    }
}

 void inOrder(BSTNode *root){
    while(root != NULL){
       preOrder(root->left);
       cout<<root->data<<endl;
       preOrder(root->right);
    }
}