In: Computer Science
Design a nonrecursive post order traversal algorithm.
1.Use the linked representation for the binary tree to be traversed.
2.Except left, right, and data fields, there are no other fields in a node.
3.After the traversal the tree should remain intact.
4.Use only one stack.
5.You can’t push anything other than nodes into the stack.
#include<stdio.h> #include<stdlib.h> #define MAXSIZE 10 struct BinaryTreeNode { int data; struct BinaryTreeNode *left; struct BinaryTreeNode *right; }; struct Queue { struct BinaryTreeNode *node; struct Queue *next; }; struct ArrayStack { int top; int capacity; struct BinaryTreeNode **array; }; struct ArrayStack *CreateStack() { struct ArrayStack *S = malloc(sizeof(struct ArrayStack)); if(!S) { return NULL; } S -> capacity = MAXSIZE; S -> top = -1; S -> array = malloc(S -> capacity * sizeof(struct BinaryTreeNode)); if(!S -> array) { return NULL; } return S; } int IsEmptyStack(struct ArrayStack *S) { return S -> top == -1; } int IsFullStack(struct ArrayStack *S) { return S -> top == S -> capacity - 1; } void Push(struct ArrayStack *S, struct BinaryTreeNode *data) { if(IsFullStack(S)) { printf("Stack Overflow\n"); } else { S -> array[++S -> top] = data; } } void Pop(struct ArrayStack *S) { if(IsEmptyStack(S)) { printf("Stack is Empty\n"); } else { S -> array[S -> top--]; } } struct BinaryTreeNode *Top(struct ArrayStack *S) { return S -> array[S -> top]; } void DeleteStack(struct ArrayStack *S) { if(S) { if(S -> array) { free(S->array); } free(S); } } struct Queue *Q = NULL; struct BinaryTreeNode *root = NULL; void EnQueue(struct BinaryTreeNode *node) { struct Queue *newNode = (struct Queue*)malloc(sizeof(struct Queue)); newNode->node = node; newNode->next = NULL; if(Q == NULL) { Q = newNode; } else { struct Queue *current; current = Q; while(current->next!=NULL) { current = current -> next; } current->next = newNode; } } struct BinaryTreeNode* DeQueue() { if(Q == NULL) { return NULL; } else { struct Queue *current; current = Q; Q = Q->next; return current->node; } } int IsEmptyQueue() { if(Q == NULL) { return 1; } else { return 0; } } void InsertInBinaryTree(int data) { struct BinaryTreeNode *temp; struct BinaryTreeNode *newNode; newNode = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode)); newNode->data = data; newNode->left = newNode->right = NULL; if(root == NULL) { root = newNode; return; } else { EnQueue(root); while(!IsEmptyQueue()) { temp = DeQueue(); if(temp->left) { EnQueue(temp->left); } else { temp->left = newNode; Q = NULL; return; } if(temp->right) { EnQueue(temp->right); } else { temp->right = newNode; Q = NULL; return; } } } Q = NULL; } void PostOrderNonRecursive(struct BinaryTreeNode *root) { struct ArrayStack *S = CreateStack(); struct BinaryTreeNode *previous = NULL; do { while(root != NULL) { Push(S,root); root = root-> left; } while(root == NULL && !IsEmptyStack(S)) { root = Top(S); if(root -> right == NULL || root -> right == previous) { printf("%d->",root->data); Pop(S); previous = root; root = NULL; } else { root = root -> right; } } }while(!IsEmptyStack(S)); printf("\n"); } int main() { InsertInBinaryTree(1); InsertInBinaryTree(2); InsertInBinaryTree(3); InsertInBinaryTree(4); InsertInBinaryTree(5); InsertInBinaryTree(6); InsertInBinaryTree(7); PostOrderNonRecursive(root); }
If you have any doubts please feel free to ask in comments and please don't dislike.