BINARY TREE TRAVERSING IN ZZ WAY
#include<stdio.h>
#include<conio.h>
struct node
{
struct node* left;
struct node* right;
int data;
};
struct snode
{
struct node *t;
struct snode *next;
};
// creation of new tree node
struct node* newnode(int value)
{
struct node* new_node;
new_node=(struct node*)malloc(sizeof(struct node));
new_node->data=value;
new_node->left=NULL;
new_node->right=NULL;
return new_node;
}
int isempty(struct snode* stacknode)
{
/* First run the code with outer while loop in the zigzag fn() get commented
* then modify the number 28482 accordingly */
return ((stacknode->t->data==28482))? 1 : 0;
}
// pushing the tree node into the stack
void push(struct snode** stknode,struct node* treenode)
{
struct snode* new_stknode=(struct snode*)malloc(sizeof(struct snode));
if(new_stknode==NULL)
{
printf("Stack Memory Allocation Error!!");
exit(0);
}
//allocation of value to new stack node
new_stknode->t = treenode;
//pushing the new tree node to the stack
if(*stknode == 0)
new_stknode->next=NULL;
else
new_stknode->next=(*stknode);
//moving the pointer to the beginning of the stack
(*stknode) = new_stknode;
}
// poping the node from the stack
struct node* pop(struct snode** stknode)
{
struct node* result;
struct snode* top;
//checking for emptyness of the stack
if(isempty(*stknode)
)
{
printf("\n Stack underflow error!");
exit(0);
return NULL;
}
else
{
top = (*stknode);
result=top->t;
*stknode = top->next;
free(top);
return result;
}
}
//prints the tree in zig-zag fashion
void zigzag(struct node* root)
{
struct snode *node1 = NULL;
struct snode *node2 = NULL;
struct node *temp=NULL;
if(root==NULL)
return;
// pushing root node to node1 stack
push(&node1,root);
isempty(node1->next);
printf("Value to be given in isemptylist() fn %d\n ",node1->next->t->data);
//loop has to run until both the stack becomes empty
/* First run the code with full outer while loop get commented
* then modify the number (here it is 28482) in the isemptylist fn() accordingly */
while(!isempty(node1) || !isempty(node2))
{
//traversing odd level left to right
while(!isempty(node1))
{
temp=pop(&node1);
printf("%d ",temp->data);
push(&node2,temp->left);
push(&node2,temp->right);
}
//traversing even level from right to left
while(!isempty(node2))
{
temp=pop(&node2);
printf("%d ",temp->data);
push(&node1,temp->right);
push(&node1,temp->left);
}
}
}
void main()
{
struct node* root=newnode(1);
clrscr();
root->left=newnode(2);
root->right=newnode(3);
root->left->left=newnode(4);
root->left->right=newnode(5);
root->right->left=newnode(6);
root->right->right=newnode(7);
zigzag(root);
getch();
}
No comments:
Post a Comment