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%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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
