Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort Boruvkas algorithm Bubble Sort vs Quick Sort Common Operations on various Data Structures Detect and Remove Loop in a Linked List How to Start Learning DSA Print kth least significant bit number Why is Binary Heap Preferred over BST for Priority Queue Bin Packing Problem Binary Tree Inorder Traversal Burning binary tree Equal Sum What is a Threaded Binary Tree? What is a full Binary Tree? Bubble Sort vs Merge Sort B+ Tree Program in Q language Deletion Operation from A B Tree Deletion Operation of the binary search tree in C++ language Does Overloading Work with Inheritance Balanced Binary Tree Binary tree deletion Binary tree insertion Cocktail Sort Comb Sort FIFO approach Operations of B Tree in C++ Language Recaman’s Sequence Tim Sort Understanding Data Processing Applications of trees in data structures Binary Tree Implementation Using Arrays Convert a Binary Tree into a Binary Search Tree Create a binary search tree Horizontal and Vertical Scaling Invert binary tree LCA of binary tree Linked List Representation of Binary Tree Optimal binary search tree in DSA Serialize and Deserialize a Binary Tree Tree terminology in Data structures Vertical Order Traversal of Binary Tree What is a Height-Balanced Tree in Data Structure Convert binary tree to a doubly linked list Fundamental of Algorithms Introduction and Implementation of Bloom Filter Optimal binary search tree using dynamic programming Right side view of binary tree Symmetric binary tree Trim a binary search tree What is a Sparse Matrix in Data Structure What is a Tree in Terms of a Graph What is the Use of Segment Trees in Data Structure What Should We Learn First Trees or Graphs in Data Structures All About Minimum Cost Spanning Trees in Data Structure Convert Binary Tree into a Threaded Binary Tree Difference between Structured and Object-Oriented Analysis FLEX (Fast Lexical Analyzer Generator) Object-Oriented Analysis and Design Sum of Nodes in a Binary Tree What are the types of Trees in Data Structure What is a 2-3 Tree in Data Structure What is a Spanning Tree in Data Structure What is an AVL Tree in Data Structure Given a Binary Tree, Check if it's balanced B Tree in Data Structure Convert Sorted List to Binary Search Tree Flattening a Linked List Given a Perfect Binary Tree, Reverse Alternate Levels Left View of Binary Tree What are Forest Trees in Data Structure Compare Balanced Binary Tree and Complete Binary Tree Diameter of a Binary Tree Given a Binary Tree Check the Zig Zag Traversal Given a Binary Tree Print the Shortest Path Given a Binary Tree Return All Root To Leaf Paths Given a Binary Tree Swap Nodes at K Height Given a Binary Tree Find Its Minimum Depth Given a Binary Tree Print the Pre Order Traversal in Recursive Given a Generate all Structurally Unique Binary Search Trees Perfect Binary Tree Threaded Binary Trees Function to Create a Copy of Binary Search Tree Function to Delete a Leaf Node from a Binary Tree Function to Insert a Node in a Binary Search Tree Given Two Binary Trees, Check if it is Symmetric A Full Binary Tree with n Nodes Applications of Different Linked Lists in Data Structure B+ Tree in Data Structure Construction of B tree in Data Structure Difference between B-tree and Binary Tree Finding Rank in a Binary Search Tree Finding the Maximum Element in a Binary Tree Finding the Minimum and Maximum Value of a Binary Tree Finding the Sum of All Paths in a Binary Tree Time Complexity of Selection Sort in Data Structure How to get Better in Data Structures and Algorithms Binary Tree Leaf Nodes Classification of Data Structure Difference between Static and Dynamic Data Structure Find the Union and Intersection of the Binary Search Tree Find the Vertical Next in a Binary Tree Finding a Deadlock in a Binary Search Tree Finding all Node of k Distance in a Binary Tree Finding Diagonal Sum in a Binary Tree Finding Diagonal Traversal of The Binary Tree Finding In-Order Successor Binary Tree Finding the gcd of Each Sibling of the Binary Tree Greedy Algorithm in Data Structure How to Calculate Space Complexity in Data Structure How to find missing numbers in an Array Kth Ancestor Node of Binary Tree Minimum Depth Binary Tree Mirror Binary Tree in Data Structure Red-Black Tree Insertion Binary Tree to Mirror Image in Data Structure Calculating the Height of a Binary Search Tree in Data Structure Characteristics of Binary Tree in Data Structure Create a Complete Binary Tree from its Linked List Field in Tree Data Structure Find a Specified Element in a binary Search Tree Find Descendant in Tree Data Structure Find Siblings in a Binary Tree Given as an Array Find the Height of a Node in a Binary Tree Find the Second-Largest Element in a Binary Tree Find the Successor Predecessor of a Binary Search Tree Forest of a Tree in Data Structure In Order Traversal of Threaded Binary Tree Introduction to Huffman Coding Limitations of a Binary Search Tree Link State Routing Algorithm in Data Structure Map Reduce Algorithm for Binary Search Tree in Data Structure Non-Binary Tree in Data Structure Quadratic Probing Example in Hashing Scope and Lifetime of Variables in Data Structure Separate Chaining in Data Structure What is Dynamic Data Structure Separate Chaining vs Open Addressing Time and Space Complexity of Linear Data Structures Abstract Data Types in Data Structures Binary Tree to Single Linked List Count the Number of Nodes in the Binary Tree Count Total No. of Ancestors in a Binary Search Tree Elements of Dynamic Programming in Data Structures Find cost of tree with prims algorithm in data structures Find Preorder Successor in a Threaded Binary Tree Find Prime Nodes Sum Count in Non-Binary Tree Find the Right Sibling of a Binary Tree with Parent Pointers Find the Width of the Binary Search Tree Forest trees in Data Structures Free Tree in Data Structures Frequently asked questions in Tree Data Structures Infix, Postfix and Prefix Conversion Time Complexity of Fibonacci Series What is Weighted Graph in Data Structure Disjoint Set ADT in Data Structure Binary Tree to Segment Tree Binary Tree to List in Order State Space Tree for 4 Queen Problem Hash Function Booth Algorithm Flowchart What is an Algorithm Master Theorem Top-down and Bottom-up Approach in Data Structure Base Address of Array Insertion into a Max Heap in Data Structure Delete a Node From Linked List Find Loop in Linked List How to implement Forward DNS Lookup Cache? How to Implement Reverse DNS Look Up Cache? Primitive vs non primitive data structure Concurrency Algorithms GCD Using Recursion Priority Queue using Linked List Difference between Array and Structure Conversion of Binary to Gray Code

Expression Tree in Data Structure
2023-05-10 23:36:58

Expression Tree in Data Structure

An expression tree is a binary tree data structure that is used to represent expressions in a mathematical or logical form. It is built from individual operands and operators, where each node of the tree represents either an operand or an operator.

In an expression tree, the leaves of the tree represent the individual operands, while the internal nodes represent the operators. The expression tree is built such that the operators are placed at the internal nodes, and the operands are placed at the leaves.

The expression tree can be used to evaluate the expression, and it can also be used to generate the equivalent prefix, infix, and postfix notations of the expression.

For example, consider the infix expression "(2+3)*(4-1)". The corresponding expression tree would be:

          *
         /   \
        +     -
       / \     / \
       2  3  4  1

In this expression tree, the internal nodes represent the operators, while the leaves represent the operands. The evaluation of the expression can be done by traversing the expression tree in a postorder traversal and performing the operations at the internal nodes.

Uses of Expression Tree in Data Structure

The expression tree data structure has several uses in computer science and programming, including:

  • Evaluating expressions: The expression tree can be used to evaluate expressions, including arithmetic, logical, and Boolean expressions. The evaluation can be done by traversing the tree in a postorder traversal and performing the appropriate operations at each internal node.
  • Simplifying expressions: The expression tree can be used to simplify expressions by performing algebraic manipulations, such as factoring, expanding, and cancelling out terms. The simplification can be done by manipulating the nodes of the tree and creating a new expression tree.
  • Generating code: The expression tree can be used to generate code for a given expression. This is particularly useful in compilers, where the expression tree can be converted into machine code or assembly language.
  • Parsing expressions: The expression tree can be used to parse expressions and convert them into a form that is easier to work with. This is useful in applications such as query languages and regular expressions.
  • Visualization: The expression tree can be used to visualize expressions, which can aid in understanding and debugging complex expressions. The tree can be displayed using graphical tools, such as tree diagrams and graph visualization software.

Types of Expression Trees

There are several types of expression trees, depending on the type of expression being represented. Some of the common types of expression trees are:

  • Arithmetic expression tree: This type of expression tree is used to represent arithmetic expressions, such as addition, subtraction, multiplication, and division. The internal nodes of the tree represent the arithmetic operators, while the leaf nodes represent the operands.
  • Boolean expression tree: This type of expression tree is used to represent Boolean expressions, such as AND, OR, NOT, and XOR. The internal nodes of the tree represent the Boolean operators, while the leaf nodes represent the Boolean values (True or False).
  • Prefix expression tree: This type of expression tree is used to represent expressions in prefix notation, where the operator appears before the operands. The internal nodes of the tree represent the operators, while the leaf nodes represent the operands.
  • Postfix expression tree: This type of expression tree is used to represent expressions in postfix notation, where the operator appears after the operands. The internal nodes of the tree represent the operators, while the leaf nodes represent the operands.
  • Infix expression tree: This type of expression tree is used to represent expressions in infix notation, where the operator appears between the operands. The internal nodes of the tree represent the operators, while the leaf nodes represent the operands.
  • Function expression tree: This type of expression tree is used to represent expressions that involve functions, such as trigonometric functions, logarithmic functions, and exponential functions. The internal nodes of the tree represent the function operators, while the leaf nodes represent the arguments.

How to Create an Expression Tree in C

To create an expression tree in C, you can follow these steps:

1. Define a node structure for the expression tree, which should have pointers to its left and right subtrees, as well as a value field to store the operand or operator.

struct TreeNode {
    char value;
    struct TreeNode* left;
    struct TreeNode* right;
};

2. Write a function to create a new node for the expression tree. The function should allocate memory for the new node, set its value to the given operand or operator, and initialize its left and right subtrees to NULL.

struct TreeNode* createNode(char value) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->value = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

3. Write a function to build the expression tree from a given postfix expression. The function should use a stack to keep track of the operands and operators, and build the expression tree by popping operands and operators from the stack and adding them as nodes to the tree.

struct TreeNode* buildExpressionTree(char postfix[]) {
    int length = strlen(postfix);
    struct TreeNode* stack[length];
    int top = -1;
    for (int i = 0; i < length; i++) {
        if (isdigit(postfix[i])) {
            struct TreeNode* operand = createNode(postfix[i]);
            stack[++top] = operand;
        }
        else {
            struct TreeNode* operator = createNode(postfix[i]);
            operator->right = stack[top--];
            operator->left = stack[top--];
            stack[++top] = operator;
        }
    }
    return stack[top];
}

4. To test the expression tree, you can write a function to evaluate the expression tree by traversing it in a postorder traversal and performing the appropriate operations at each internal node.

int evaluateExpressionTree(struct TreeNode* root) {
    if (!root)
        return 0;
    if (!root->left && !root->right)
        return root->value - '0';
    int leftOperand = evaluateExpressionTree(root->left);
    int rightOperand = evaluateExpressionTree(root->right);
    switch (root->value) {
        case '+': return leftOperand + rightOperand;
        case '-': return leftOperand - rightOperand;
        case '*': return leftOperand * rightOperand;
        case '/': return leftOperand / rightOperand;
    }
    return 0;
}

Overall, creating an expression tree in C involves defining the node structure, writing functions to create nodes and build the tree, and testing the tree by evaluating its expression.

Evaluation of an Expression Tree

Evaluation of an expression tree involves traversing the tree and performing the appropriate operations at each internal node to compute the final result of the expression. The following steps can be followed to evaluate an expression tree:

  • Traverse the expression tree in a postorder traversal.
  • If the current node is a leaf node, return its value.
  • If the current node is an internal node, recursively evaluate its left and right subtrees.
  • Perform the appropriate operation at the current node, based on its value.
  • Return the final result of the expression.

Implementation of Expression Tree in C++

Here is an implementation of an expression tree in C++:

#include <iostream>
#include <stack>
#include <string>
#include <cctype>


using namespace std;


// Define the node structure for the expression tree
struct TreeNode {
    char value;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char val) : value(val), left(NULL), right(NULL) {}
};


// Create a new node for the expression tree
TreeNode* createNode(char value) {
    return new TreeNode(value);
}


// Build the expression tree from a given postfix expression
TreeNode* buildExpressionTree(string postfix) {
    stack<TreeNode*> st;
    for (int i = 0; i < postfix.size(); i++) {
        char c = postfix[i];
        if (isdigit(c)) {
            TreeNode* operand = createNode(c);
            st.push(operand);
        }
        else {
            TreeNode* op = createNode(c);
            op->right = st.top(); st.pop();
            op->left = st.top(); st.pop();
            st.push(op);
        }
    }
    return st.top();
}


// Evaluate the expression tree
int evaluateExpressionTree(TreeNode* root) {
    if (!root)
        return 0;
    if (!root->left && !root->right)
        return root->value - '0';
    int leftOperand = evaluateExpressionTree(root->left);
    int rightOperand = evaluateExpressionTree(root->right);
    switch (root->value) {
        case '+': return leftOperand + rightOperand;
        case '-': return leftOperand - rightOperand;
        case '*': return leftOperand * rightOperand;
        case '/': return leftOperand / rightOperand;
    }
    return 0;
}


// Test the expression tree
int main() {
    string postfix = "45+7*";
    TreeNode* root = buildExpressionTree(postfix);
    int result = evaluateExpressionTree(root);
    cout << "Result: " << result;}

Output:

/tmp/XWvNMi4nJR.o
Result: 63

Generation of Expression Tree

The process of generating an expression tree involves constructing a tree data structure from an expression in infix notation. The general steps to generate an expression tree are as follows:

  • Convert the infix expression to postfix notation using the shunting yard algorithm or a similar method.
  • Create an empty stack to hold the nodes of the expression tree.
  • Traverse the postfix expression from left to right.
  • For each operand, create a leaf node with the operand as its value and push it onto the stack.
  • For each operator, pop the top two nodes from the stack and create a new internal node with the operator as its value and the two nodes as its left and right children. Push the new node onto the stack.
  • Repeat steps 4 and 5 until the end of the postfix expression is reached.
  • The final node left on the stack is the root of the expression tree.