It looks like it might work, but it requires marks on the nodes. So
it's not what you want. Here is the algorithm for _all_ the orders:
void si(NODE *tree)
{
restart:
while (tree) {
printf("preorder %d\n", tree->val);
PUSH(tree, 0);
tree = tree->left;
}
while (sp) {
if (POP(tree) == 0) {
printf("inorder %d\n", tree->val);
PUSH(tree, 1);
tree = tree->right;
goto restart;
}
printf("postorder %d\n", tree->val);
}
}
On Jun 19, 10:59 am, divya jain <[email protected]> wrote:
> /*
> Assuming you have a stack setup with push() and pop() operations.
> Also assuming that all nodes are initially marked to 0.
> (This function will reset them back to zero when finished)
> */
> void postorder(Node *n) {
> push(n);
>
> while (stack.size > 0) {
> n = (Node*)pop();
>
> if (n->marked || (n->left == NULL && n->right == NULL)) {
> n->marked = 0;
> printf("%d\n", n->value);
> }
> else {
> n->marked = 1;
> push(n);
>
> if (n->right) push(n->right);
> if (n->left) push(n->left);
> }
> }
>
> }
>
> is the above solution fine for postorder. plz let me knw if there is any
> mistake........
>
> On 17 June 2010 10:37, Gene <[email protected]> wrote:
>
>
>
> > On Jun 16, 3:01 pm, divya <[email protected]> wrote:
> > > plz give algos of inorder, preorder nd post order tree traversal..non
> > > recursive one..using stack..
> > > nd the tree is not threaded
>
> > #include <stdio.h>
> > #include <stdlib.h>
>
> > typedef struct node_s {
> > int val;
> > struct node_s *left, *right;
> > } NODE;
>
> > NODE *new(int val)
> > {
> > NODE *tree = malloc(sizeof(NODE));
> > tree->val = val;
> > tree->left = tree->right = NULL;
> > return tree;
> > }
>
> > void search(NODE *tree)
> > {
> > if (tree) {
> > printf("preorder %d\n", tree->val);
> > search(tree->left);
> > printf("inorder %d\n", tree->val);
> > search(tree->right);
> > printf("postorder %d\n", tree->val);
> > }
> > }
>
> > // Direct conversion of recursive code to iteration.
> > struct stack_elt_s {
> > int site;
> > NODE *tree;
> > } stack[100];
> > int sp = 0;
>
> > void search_iterative(NODE *tree) {
> > start:
> > if (tree) {
> > printf("preorder %d\n", tree->val);
> > // simulate the recursive call search(tree->left)
> > stack[sp].tree = tree;
> > stack[sp++].site = 0;
> > tree = tree->left;
> > goto start;
> > L0:
> > printf("inorder %d\n", tree->val);
> > // simulate the recursive call search(tree->right)
> > stack[sp].tree = tree;
> > stack[sp++].site = 1;
> > tree = tree->right;
> > goto start;
> > L1:
> > printf("postorder %d\n", tree->val);
> > }
> > // simulate return to last call site
> > if (sp) {
> > tree = stack[--sp].tree;
> > switch (stack[sp].site) {
> > case 0: goto L0;
> > case 1: goto L1;
> > }
> > }
> > }
>
> > int main(void)
> > {
> > struct node_s *n0 = new(0);
> > struct node_s *n1 = new(1);
> > struct node_s *n2 = new(2);
> > struct node_s *n3 = new(3);
> > struct node_s *n4 = new(4);
> > n0->left = n1;
> > n0->right = n2;
> > n1->left = n3;
> > n2->left = n4;
>
> > printf("recusive:\n");
> > search(n0);
>
> > printf("\nnow iterative:\n");
> > search_iterative(n0);
>
> > return 0;
> > }
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected]<algogeeks%2bunsubscr...@googlegroups
> > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
