Sorry in the do while loop p!=NULL shudn't appear
On Sun, Jul 4, 2010 at 12:29 AM, Raj N <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 <[email protected]> wrote:
>> >
>> > > > On Jun 16, 3:01 pm, divya <[email protected]> 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 [email protected].
>> > > > To unsubscribe from this group, send email to
>> > > > [email protected]<algogeeks%[email protected]>
>> <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 [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.
