Pre order traversal with and without recursion.

Program for pre order traversal with and without recursion.

// PreOrderTraversal.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "string.h"
#include "stdlib.h"
#include "malloc.h"

//Definition of all the variables
struct Node;
typedef struct Node{
struct Node* Left;
char CharData;
struct Node* Right;
}NODE;

struct Stk;
typedef struct Stk{
char CharData;
NODE* TreeNode;
}STK;

struct List;
typedef struct List LIST;
struct List{
STK* StkPtr;
LIST* Next;
};
char Tree[100];
STK* Stack[100];
NODE* Stack2[100];
int top = -1;
int top2 = -1;
LIST* HeadOfList=0;

//Definition of functions
NODE* ParseAndConstructTree();
void CollectAllTheChildren(STK * ch);
NODE* CreateATreeWithCurrentNode(char ch);
void Push(char ch);
void PushStkPtr(STK * ch);
void PushStk2(NODE* nd);
NODE* PopStk2();
STK* Pop();
STK* Peek();
int ConvertCharToInt( char ch);
char GetChar(STK * ch);
void PreOrderWithoutRecursion(NODE * node);
void PreOrderWithRecursion(NODE * node);

void PreOrderWithRecursion(NODE * node)
{
if (node != 0)
{
printf (" %c ",node->CharData);
PreOrderWithRecursion(node->Left);
PreOrderWithRecursion(node->Right);
}
}

bool IsStk2Empty()
{
return (top2 == -1);
}

void PreOrderWithoutRecursion(NODE * node)
{
NODE * Top = node;
while (Top != 0)
{
while (node != 0)
{
printf (" %c ", node->CharData);
PushStk2(node);
node = node->Left;
}
if (IsStk2Empty())
break;
Top = PopStk2();
node = Top->Right;
}
}

void PushStk2(NODE* nd)
{
if (top2 == 99)
{
printf ("\n Second Stack is full \n");
exit(0);
}
Stack2[++top2] = nd;
}

NODE* PopStk2()
{
if (top2 == -1)
{
printf("\n Second Stack is empty \n");
exit(0);
}
return Stack2[top2--];
}

int _tmain(int argc, _TCHAR* argv[])
{
char ch;
NODE* Root;
printf("Enter the Tree in following format\n");
printf("m(a(bc)d(ef))\n");
scanf("%s",Tree);
Root = ParseAndConstructTree();
printf ("InOrder without Recursion \n");
PreOrderWithoutRecursion(Root);
printf ("\n InOrder with Recursion \n");
PreOrderWithRecursion(Root);
fflush(stdin);
scanf("%c",&ch);
return 0;
}

NODE* ParseAndConstructTree()
{
size_t TreeLength;
STK* c;
TreeLength = strlen(Tree);
for (size_t i=0;iTreeNode = tree;
PushStkPtr(StkTop);
}
}
return Pop()->TreeNode;
}

void Push(char ch)
{
if (top == 99)
{
printf("Stack is full\n");
exit(0);
}
//Create a STK memory and insert into the Stack array.
STK * StackNode = (STK*) malloc(sizeof(STK));
NODE* TreeNode = (NODE*) malloc(sizeof(NODE));
TreeNode->CharData = ch;
TreeNode->Left = 0;
TreeNode->Right = 0;
StackNode->CharData = ch;
StackNode->TreeNode = TreeNode;
Stack[++top] = StackNode;
}

void PushStkPtr(STK* ch)
{
if (top == 99)
{
printf("Stack is full\n");
exit(0);
}
Stack[++top] = ch;
}

STK* Pop()
{
if (top == -1)
{
printf("Stack is empty\n");
exit(0);
}
return Stack[top--];
}

STK* Peek()
{
if (top == -1)
{
printf("Stack is empty\n");
exit(0);
}
return Stack[top];
}

char GetChar(STK * ch)
{
return ch->CharData;
}

void CollectAllTheChildren(STK *ch)
{
//create a LIST node
LIST* l = (LIST*) malloc(sizeof(LIST));
l->StkPtr = ch;
l->Next = HeadOfList;
HeadOfList = l;
}

NODE* CreateATreeWithCurrentNode(char ch)
{
//create tree node
NODE* treenode = (NODE*) malloc(sizeof(NODE));
treenode->CharData = ch;
if (HeadOfList)
treenode->Left = HeadOfList->StkPtr->TreeNode;
else
treenode->Left = 0;
if (HeadOfList->Next)
treenode->Right = HeadOfList->Next->StkPtr->TreeNode;
else
treenode->Right = 0;
return treenode;
}