Post order traversal with and without recursion.

Here is the program for post order traversal using with and without recursion.

// PostOrderTraversal.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 cnt[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(int * ct);

STK* Pop();

STK* Peek();

int ConvertCharToInt( char ch);

char GetChar(STK * ch);

void PostOrderWithoutRecursion(NODE * node);

void PostOrderWithRecursion(NODE * node);

void PostOrderWithRecursion(NODE * node)

{

if (node != 0)

{

PostOrderWithRecursion(node->Left);

PostOrderWithRecursion(node->Right);

printf (" %c ",node->CharData);

}

}

bool IsStk2Empty()

{

return (top2 == -1);

}

void PostOrderWithoutRecursion(NODE * node)

{

int ct=0;

NODE * Top = node;

while (Top != 0)

{

while (node != 0)

{

PushStk2(node);

node = node->Left;

}

if (IsStk2Empty())

break;

Top = PopStk2(&ct);

if (ct )

printf (" %c ",Top->CharData);

else

node = Top->Right;

}

}

void PushStk2(NODE* nd)

{

if (top2 == 99)

{

printf ("\n Second Stack is full \n");

exit(0);

}

Stack2[++top2] = nd;

cnt[top2] = 0;

}

NODE* PopStk2(int *ct)

{

if (top2 == -1)

{

printf("\n Second Stack is empty \n");

exit(0);

}

if (cnt[top2])

{

*ct = 1;

cnt[top2] = 0;

return Stack2[top2--];

}

else

{

cnt[top2] = 1;

*ct = 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 ("PostOrder without Recursion \n");

PostOrderWithoutRecursion(Root);

printf ("\n PostOrder with Recursion \n");

PostOrderWithRecursion(Root);

fflush(stdin);

scanf("%c",&ch);

return 0;

}

NODE* ParseAndConstructTree()

{

size_t TreeLength;

STK* c;

TreeLength = strlen(Tree);

for (size_t i=0;i

{

if (Tree[i] != ')')

Push(Tree[i]);

else

{

while (GetChar(c=Pop()) != '(')

CollectAllTheChildren(c);

NODE* tree = CreateATreeWithCurrentNode(GetChar(Peek()));

STK* StkTop = Pop();

StkTop->TreeNode = 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;

}