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> > > > . > > > 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.