Question

In: Computer Science

Design a nonrecursive post order traversal algorithm. 1.Use the linked representation for the binary tree to...

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.

Solutions

Expert Solution

#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.


Related Solutions

Create a Binary Search Tree for the following data and do In-order, Preorder and Post-order traversal...
Create a Binary Search Tree for the following data and do In-order, Preorder and Post-order traversal of the tree. 50, 60, 25, 40, 30, 70, 35, 10, 55, 65, 5 Write an algorithm to delete a node in Singly Linked List                            [12 Write an algorithm of Binary Search                                                              [10] Write a program in ‘C’ to generate Fibonacci series using recursion            [8]
Exercise 1: (Divide and Conquer: Binary tree traversal) Write pseudocode for one of the classic traversal...
Exercise 1: (Divide and Conquer: Binary tree traversal) Write pseudocode for one of the classic traversal algorithms (preorder, inorder, and postorder) for binary trees. Assuming that your algorithm is recursive, find the number of recursive calls made.
Make an Array implementation of a binary tree given the below class ArrayBinaryTree(BinaryTree): """Linked representation of...
Make an Array implementation of a binary tree given the below class ArrayBinaryTree(BinaryTree): """Linked representation of a binary tree structure.""" # -------------------------- nested _Node class -------------------------- class _Node: def __init__(self, element, parent=None, left=None, right=None): # -------------------------- nested Position class -------------------------- class Position(BinaryTree.Position): """An abstraction representing the location of a single element.""" def __init__(self, container, node): def element(self): def __eq__(self, other): # ------------------------------- utility methods ------------------------------- def _validate(self, p): """Return associated node, if position is valid.""" def _make_position(self, node): """Return Position...
P1. Construct the tree with post-order traversal string = i b d a h g c...
P1. Construct the tree with post-order traversal string = i b d a h g c f, and in-order traversal string = b i a d f g h c. P2. Construct the tree with pre-order traversal string = 10, 20, 40, 50, 80, 60, 70, 90, and in-order traversal string = 40, 50, 20, 10, 80, 70, 90, 60.
in C programming Write the code to traverse the binary tree using in-order, post-order and pre-order...
in C programming Write the code to traverse the binary tree using in-order, post-order and pre-order methods. Make sure to validate that your output is correct. Review the terminology for tree structures and list structures. What is the root of the tree, what’s a parent, what’s a child, what’s an ancestor, what is an external node, what is an internal node, what is the head of the list, what is the tail of the list, etc. Traverse the binary tree...
Write the binary tree representation for the Binary Search for also 17 elements and give the...
Write the binary tree representation for the Binary Search for also 17 elements and give the worst-case
Let T be a binary tree with n positions that is realized with an array representation...
Let T be a binary tree with n positions that is realized with an array representation A, and let f() be the level numbering function of the positions of T, as given in Section 8.3.2. Give pseudocode descriptions of each of the methods root, parent, left, right, isExternal, and isRoot.
Binary Tree Create a binary search tree using the given numbers in the order they’re presented....
Binary Tree Create a binary search tree using the given numbers in the order they’re presented. State if the resulting tree is FULL and/or BALANCED. 37, 20, 18, 56, 40, 42, 12, 5, 6, 77, 20, 54
In MobaXterm, with the use of the binary search tree. Implement four operations of insert, in-order...
In MobaXterm, with the use of the binary search tree. Implement four operations of insert, in-order traversal, preorder traversal, and find. Please separate the code in the four parts and explain in detail what is happening. Also, if you can please basic C language. If not, then I understand. Thank you for your time. The test cases are 'm', 'd', 'g', 'r', 'p', 'b', and 'x'. Output: Enter choice (lower case is also acceptable) --- (I)nsert, (F)ind, (Q)uit: i Enter...
C++ tree program (do NOT use STRUCT, use classes)    Program 1 Implement a Binary tree...
C++ tree program (do NOT use STRUCT, use classes)    Program 1 Implement a Binary tree using an array    Program 2 Implement a tree using linked list - pointer Binary Tree    Program 3 - Convert program 1 to a template
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT