/*
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%[email protected]>
> .
> 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.
