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.
