Prerequisite: Expression Tree
The expression tree is a binary tree in which each internal node corresponds to the operator and each leaf node corresponds to the operand so for example expression tree for 3 + ((5+9)*2) would be:
In expression trees, leaf nodes are operands and non-leaf nodes are operators. That means an expression tree is a binary tree where internal nodes are operators and leaves are operands. An expression tree consists of binary expressions. But for a unary operator, one subtree will be empty.Â
Construction of Expression Tree:
- The user will provide a postfix expression for which the program will construct the expression tree.Â
- Inorder traversal of binary tree/expression tree will provide Infix expression of the given input.
Example:Â Â
Input: A B C*+ D/ Output: A + B * C / D
Step 1: The first three symbols are operands, so create tree nodes and push pointers to them onto a stack as shown below.
Step 2: In the Next step, an operator ‘*’ will going read, so two pointers to trees are popped, a new tree is formed and a pointer to it is pushed onto the stack
Step 3: In the Next step,  an operator ‘+’ will read, so two pointers to trees are popped, a new tree is formed and a pointer to it is pushed onto the stack.
Step 4: Similarly, as above cases first we push ‘D’ into the stack and then in the last step first, will read ‘/’ and then as previous step topmost element will pop out and then will be right subtree of root  ‘/’ and other node will be right subtree.
Final Constructed Expression Tree is:
Below is the C++ program to implement the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;class node {public:Â Â Â Â char value;Â Â Â Â node* left;Â Â Â Â node* right;Â Â Â Â node* next = NULL;Â Â Â Â node(char c)Â Â Â Â {Â Â Â Â Â Â Â Â this->value = c;Â Â Â Â Â Â Â Â left = NULL;Â Â Â Â Â Â Â Â right = NULL;Â Â Â Â }Â Â Â Â node()Â Â Â Â {Â Â Â Â Â Â Â Â left = NULL;Â Â Â Â Â Â Â Â right = NULL;Â Â Â Â }Â Â Â Â friend class Stack;Â Â Â Â friend class expression_tree;};Â
// Class stack to hold// tree nodesclass Stack {Â Â Â Â node* head = NULL;Â
public:Â Â Â Â void push(node*);Â Â Â Â node* pop();Â Â Â Â friend class expression_tree;};Â
// Class to implement// inorder traversalclass expression_tree {public:    // Function to implement    // inorder traversal    void inorder(node* x)    {        if (x == NULL)            return;        else {            inorder(x->left);            cout << x->value << " ";            inorder(x->right);        }    }};Â
// Function to push values// onto the stackvoid Stack::push(node* x){Â Â Â Â if (head == NULL) {Â Â Â Â Â Â Â Â head = x;Â Â Â Â }Â
    // We are inserting nodes at    // the top of the stack [    // following LIFO principle]    else {        x->next = head;        head = x;    }}Â
// Function to implement pop// operation in the stacknode* Stack::pop(){    // Popping out the top most[    // pointed with head] element    node* p = head;    head = head->next;    return p;}Â
// Driver codeint main(){    // Postfix expression    string s = "ABC*+D/";Â
    Stack e;    expression_tree a;    node *x, *y, *z;    int l = s.length();Â
    for (int i = 0; i < l; i++) {        // if read character is operator        // then popping two other elements        // from stack and making a binary        // tree        if (s[i] == '+' || s[i] == '-'            || s[i] == '*' || s[i] == '/'            || s[i] == '^') {            z = new node(s[i]);            x = e.pop();            y = e.pop();            z->left = y;            z->right = x;            e.push(z);        }        else {            z = new node(s[i]);            e.push(z);        }    }Â
    // Print the inorder traversal    cout << " The Inorder Traversal of Expression Tree: ";    a.inorder(z);    return 0;} |
The Inorder Traversal of Expression Tree: A + B * C / D
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Find More here to that Topic: geeksforgeeks.org/expression-trees-using-classes-in-c-with-implementation/ […]
… [Trackback]
[…] Read More Info here on that Topic: geeksforgeeks.org/expression-trees-using-classes-in-c-with-implementation/ […]