Please adjust this code, MUST NOT use c++ library for stack and queue

and the expression tree for the node that has null children should print empty space or symbol , the output must be look like this (Don't forget the space between each node)

CODE:-

/*

The following program works by coverting the postfix notation into the corresponding tree which is the traversed in a level order fashion.

*/

#include //Includes all the header files including stl

using namespace std;

struct Node{

char data; //To store the operators or operands of a Node

Node *left, *right; //To store the left and right child of a Node

//Constructor that takes the character value as a parameter and makes the left and right child as NULL

Node(char x)

{

data = x; //makes the data to be x

//make the left and right child as NULL

left = NULL;

right = NULL;

}

};

/*

isOperator checks if a character is an operator or not by returning a bool value

true - if the character is an operator

false - otherwise

*/

bool isOperator(char x)

{

if(x == '+' || x == '-' || x == '/' || x == '*') //all operators possible

{

return true; //if operator return true

}

return false; //else return false

}

/*constructTree() is a function that takes the postfix expression as the parameter and converts it to the corresponding tree returning the address of the root node

*/

Node* constructTree(string postfix)

{

/*

stack to simultaneously convert the postfix notation to the infix notation and also to construct the tree in a bottom up manner

*/

stack st;

//Temporary nodes to process the nodes in the tree

Node *tmp, *t1, *t2;

for(int i=0; i

{

if(!isOperator(postfix[i]))

//check if the ith character in the psotfix expression is an operator or not

{

//the ith character is an operand, hence we push a new node

tmp = new Node(postfix[i]); //create a new node of ith character

st.push(tmp); //push the new node into the stack

}

else{ //it is an operator

tmp = new Node(postfix[i]); //create a new node with data as operator

t1 = st.top(); //get the topmost element of the stack

st.pop(); //remove the topmost element

t2 = st.top();

st.pop();

tmp->left = t2; //make the left child as the 2nd to topmost operand

tmp->right = t1; //make the right child as the topmost operand

st.push(tmp); //Add the resultant node into the stack

}

}

/*

After the full traversal of the string we can obtain the root node as the top of the stack, because if the postfix expression is valid then there would be only one node left in the stack

*/

tmp = st.top();

st.pop();

return tmp;

}

/*

levelOrder() takes the root as a parameter and prints the level order traversal of the tree by using a queue and

*/

void levelOrder(Node *root)

{

queue q; //queue used to traverse the tree in level order fashion

q.push(root); //push the root node into the queue

q.push(NULL); //to indicate the end of level in the tree

while(!q.empty())

/*

q.empty() is a function that returns true if the tree is empty else returns false

thus traverse till the queue becomes empty

*/

{

Node *tmp = q.front(); //get the fronmost element of the queue

q.pop(); //remove the frontmost element

if(q.empty())

//check if the queue is empty, then the entire tree has been traversed

{

break;

}

if(tmp == NULL) // a level of the tree is complete

{

cout

q.push(NULL);

continue; //to mark the next level

}

cout

if(tmp->left != NULL)

//if there is left child of the root, then push it into queue

{

q.push(tmp->left);

}

if(tmp->right != NULL) //if there is a right child of root, then push it

{

q.push(tmp->right);

}

}

}

int main()

{

string postfix = "ABC*+AB-C*/";

Node *root = constructTree(postfix); //get the root of the construceted tree

levelOrder(root); //called to obtain the result

return 0;

}

# # D CAB # # # # D CAB # #