void preorder(NODE tree) { struct stack { int top; NODE item[MAX]; }s; NODE p; s.top=-1; p=tree; do { while(p!=NULL) { printf("%d",p->info); push(s,p); p=p->left; } if(!empty(s) { p=pop(s); p=p->right;
} } while(!empty(s) || p!=NULL); } void inorder(NODE tree) { struct stack { int top; NODE item[MAX]; }s; NODE p; s.top=-1; p=tree; do { while(p!=NULL) { push(s,p); p=p->left; } if(!empty(s) { p=pop(s); printf("%d",p->info); p=p->right; } } while(!empty(s) || p!=NULL); } void postorder(NODE tree) { struct stack { int top; NODE item[MAX]; }s; NODE p; NODE q; s.top=-1; p=tree; do { while(p!=NULL) { push(s,p); p=p->left; } if(!empty(s) { p=pop(s); if (empty(s)) { printf("%d",p->info); return; } q=pop(s); printf("%d",p->info); push(s,q); if(p==q->left) p=q->right; else p=NULL; } } while(!empty(s) || p!=NULL); } On Thu, Jul 1, 2010 at 12:14 PM, vicky <mehta...@gmail.com> wrote: > I m adding my program too, with some 2-3 added features: > > > > > #include <stdio.h> > #include <stdlib.h> > #include <string.h> > #include<conio.h> > #include<iostream> > #include <stack> > #include <algorithm> > #include <queue> > using namespace std; > // BST-node layout > typedef struct Tree{ > int data; > Tree *left; > Tree *right; > }treeObject; > // allocate memory to new node. notice pass by address of node > void AllocateMemory(treeObject **node){ > *node=new treeObject; > (*node)->left=(*node)->right=NULL; > } > // insert a new node > void Insert(treeObject *node,treeObject *root,int data){ > if(root==NULL){ > return; > } > node->data=data; > treeObject *prev=NULL; > treeObject *next=NULL; > next=prev=root; > while(next!=NULL){ > prev=next; > if(next->data<=data){ > next=next->right; > } > else{ > next=next->left; > } > } > if(prev->data<=data){ > prev->right=node; > } > else{ > prev->left=node; > } > } > //recursive inorder traversal > void RecInorder(treeObject *node){ > if(node==NULL){ > return; > } > RecInorder(node->left); > cout<<node->data<<" "; > RecInorder(node->right); > } > //recursive postorder traversal > void RecPostorder(treeObject *node){ > if(node==NULL){ > return; > } > RecInorder(node->left); > RecInorder(node->right); > cout<<node->data<<" "; > } > //recursive preorder traversal > void RecPreorder(treeObject *node){ > if(node==NULL){ > return; > } > cout<<node->data<<" "; > RecInorder(node->left); > RecInorder(node->right); > } > //Iterative Inorder traversal > void IterInorder(treeObject *node){ > stack<treeObject *> S; > treeObject *temp=node; > while(temp!=NULL){ > S.push(temp); > if(temp->left!=NULL){ > temp=temp->left; > } > else { > if(temp->left==NULL){ > if(temp->right==NULL){ > cout<<S.top()->data<<" "; > if(S.empty()){return;} > S.pop(); > if(!S.empty()){ > cout<<S.top()->data<<" "; > temp=S.top()->right; > } > if(S.empty()){return;} > S.pop(); > } > else{ > cout<<S.top()->data<<" "; > if(S.empty()){return;} > S.pop(); > temp=temp->right; > } > } > } > } > } > void BFT(treeObject *node){ > queue<treeObject *>Q; > Q.push(node); > while(!Q.empty()){ > cout<<Q.front()->data<<" "; > if(Q.front()->left)Q.push(Q.front()->left); > if(Q.front()->right)Q.push(Q.front()->right); > Q.pop(); > } > } > > int main(){ > treeObject *root; > int i=10; > AllocateMemory(&root); > root->data=0; > treeObject *node; > AllocateMemory(&node); > Insert(node,root,10); > treeObject *node1; > AllocateMemory(&node); > Insert(node,root,71); > treeObject *node2; > AllocateMemory(&node); > Insert(node,root,12); > treeObject *node3; > AllocateMemory(&node); > Insert(node,root,2); > treeObject *node4; > AllocateMemory(&node); > Insert(node,root,222); > treeObject *node5; > AllocateMemory(&node); > Insert(node,root,5); > treeObject *node6; > AllocateMemory(&node); > Insert(node,root,8); > treeObject *node7; > AllocateMemory(&node); > Insert(node,root,65); > treeObject *node8; > AllocateMemory(&node); > Insert(node,root,5); > treeObject *node9; > AllocateMemory(&node); > Insert(node,root,9); > treeObject *node10; > AllocateMemory(&node); > Insert(node,root,1); > cout<<"recursive Inorder traversal\n"; > RecInorder(root); > cout<<endl; > cout<<"recursive Postorder traversal\n"; > RecPostorder(root); > cout<<endl; > cout<<"recursive Preorder traversal\n"; > RecPreorder(root); > cout<<endl; > cout<<"iterative inorder traversal\n"; > IterInorder(root); > cout<<endl; > cout<<"Breadth First Traversal\n"; > BFT(root); > getch(); > } > > > > > > > > > > > > > > > On Jun 20, 8:17 am, Gene <gene.ress...@gmail.com> wrote: > > 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 ordertreetraversal..non > > > > > recursive one..using stack.. > > > > > nd thetreeis 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; > > > > returntree; > > > > } > > > > > > 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> > <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<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.