Sorry in the do while loop p!=NULL shudn't appear On Sun, Jul 4, 2010 at 12:29 AM, Raj N <rajn...@gmail.com> wrote:
> 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.