It might be right. But it requires marks on the nodes, so it's not a
fully general algorithm, and probably not what you want. Here is the
full algorithm that implements all the orders. Take your pick. It
does turn out that if you don't need post order, you can simplify
further. In particular, you no longer need the 1/0 flag stored on the
stack. You only need a stack of pointers.
void si(NODE *tree)
{
for (;;) {
while (tree) {
printf("preorder %d\n", tree->val);
PUSH(tree, 0);
tree = tree->left;
}
for (;;) {
if (!sp) return; // return on stack empty
if (POP(tree) == 0) {
printf("inorder %d\n", tree->val);
PUSH(tree, 1);
tree = tree->right;
break;
}
printf("postorder %d\n", tree->val);
}
}
}
On Jun 19, 10:59 am, divya jain <sweetdivya....@gmail.com> 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 <gene.ress...@gmail.com> wrote:
>
>
>
> > On Jun 16, 3:01 pm, divya <sweetdivya....@gmail.com> 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 algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
