Iterative inorder traversal BST
it outputs 7 infinite times. 7 is the smallest number in the tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
|
void iinorder(treetype *stack[], int &top, treetype *root)
{
treetype *c;
c = root;
bool done;
push(stack, top, NULL);
while(c != NULL)
{
while(c->left != NULL)
{
push(stack, top, c);
c = c->left;
}
done = false;
while(!done)
{
cout << setw(4) << c->id;
if(c->right != NULL)
{
c = c->right;
done = true;
}
else
pop(stack, top);
if(c == NULL) done = true;
}
}
}
|
¿Shouldn't you recover the value on the stack?
i actually rewrote it so the it outputs the tree in order but one it gets to the end of the output, the program crashes
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
|
treetype *iinorder(treetype *stack[], int &top, treetype *root)
{
treetype *c;
c = root;
bool done = false;
push(stack, top, NULL);
while(!done)
{
if(c != NULL)
{
push(stack, top, c);
c = c->left;
}
else
{
if(!done)
{
c = pop(stack, top);
cout << setw(4) << c->id;
c = c->right;
}
else
done = true;
}
}
return c;
}
|
That's because you are trying to pop from an empty stack.
1 2 3 4 5 6 7 8 9 10 11 12 13
|
while(!done)
{
//...
if(!done) //true
{
c = pop(stack, top);
cout << setw(4) << c->id;
c = c->right;
}
else
done = true; //never executes
}
}
|
Topic archived. No new replies allowed.