Binary tree traversal question

[Kirby]

Tree

I have to write a binary tree that outputs the post-order traversal of the tree given the pre-order and in-order, and either my program is wrong (most likely) or me writing it out is wrong. I'm pretty sure I fouled up the recursion.

This is what I get on paper
Pre: f b a d c e h g j i k
InO: a b c d e f g h i j k
Pst: a c e d b g i k j h f

Correct?

However my output is: a c g i k j h e d b f

More interesting, if I use this set:

Pre: a c x Q F r t !
InO: c a x F Q t r !
Pst: c F t ! r Q x a

I get the correct post-order. 😕

 

[Brett]

postorder(Node node){
if(node.getLeft() != null) {
postorder(node.getLeft());
}

if(node.getRight() != null) {
postorder(node.getRight());
}

System.out.println(node);
}

given your tree...

Correct: a - c - e - d - b - g - i - k - j - h - f

 

[Kirby]

In the Tree class:

void print(){
//cout<<"The printing root is: "<<(char)root->data<<endl;
root->post_print();
}

In the Node class:

void post_print(){
if(left) left->post_print();
if(right) right->post_print();
cout<< (char)data <<" ";
return;
}

Same thing?

 

[Brett]

They look the same to me... if you're still having printing problems, you might have a bug elsewhere in your Tree or Node class that is causing to generate an improper tree, and that might explain your wierd printing.

 

[Madwand1]

Can you double-check your tree structure by performing pre-order and in-order traversals and comparing the results with the inputs?

 

[Kirby]

Originally posted by: Madwand1
Can you double-check your tree structure by performing pre-order and in-order traversals and comparing the results with the inputs?

Yup, my insert algorithm is screwed up. Printing them back out in pre and in order did the trick. It's still odd that the particular one printed the post-order correctly. Must of been just a coincidence. 😕

Back to work on the algorithm. *sigh*

 

[Kirby]

Well, I still haven't got this to work correctly and I'm not sure what's going wrong. When I insert into the tree, I output which letter is being inserted and what direction (left or right) from the current pointer. And it's correct, although it does go a couple places out of the array at the end. I'd really appreciate it if someone could look this over and offer some suggestions.

What I have is 3 arrays. The first is the pre-order and the second is the inorder. The third is an array that hold the position of the inorder array. For example, in the inorder array, 'a' is in [1], so in the second array, '1' is at [97]. This makes it easier to compare the position of the characters. So here are the methods:

bool insert(char P[],int I[]){
if (root == 0)
root = new Node(P[0]);
doInsert(P,I,root,1);


}

bool doInsert(char P[], int I[], Node *ptr,int pos) {

cout<<endl<<"Current Ptr: "<<(char)ptr->data<<endl<<"POS: "<<pos<<endl;
cout<<I[(int)P[pos]]<<" "<<I[ptr->data]<<endl;

if(I[(int)P[pos]] < I[ptr->data]){cout<<"going left"<<endl;
if(ptr->left)
doInsert(P,I,ptr->left,pos);
else{cout<<"inserted "<<P[pos]<<endl;
ptr->left=new Node((int)P[pos]);pos++;
doInsert(P,I,ptr,pos);
}
}

else if(I[(int)P[pos]] > I[ptr->data]){cout<<"going right"<<endl;//to the right in I
if(ptr->right)
doInsert(P,I,ptr->right,pos);
else{cout<<"inserted "<<P[pos]<<endl;
ptr->right=new Node((int)P[pos]);pos++;
doInsert(P,I,ptr,pos);}
}



return true;
}

 

[Madwand1]

The problem is that once you find a node existing in the direction you want to go, you advance the pointer to that node, and never go back up again. This works fine for trees/subtrees which aren't large, but fails for larger ones -- which is why it seemed to work fine in one test case, and why it partially works for the other case.

Specifically, in the first case, when it's time to insert the "h", you need to be back up at the level of the "f", but that's long gone -- your algorithm puts ptr at the "e" instead. So the structure is fine for everything up to and including the "e", and the subtree below the "h" is also right, but the "h" is linked to the "e" instead of the "f'.

I would have come up with a completely different solution, so don't have a simple fix in mind for yours.

 

[Kirby]

Meh, too late now. 😛

I changed it a bit, and I think I got it to where it would output the post-order correctly, but none of pre-orders or in-orders would be right. 😕 But the assignment was for a correct post-order, so whatever.