In Data structures, trees are often used to represent hierarchical ways. One such tree is the expression tree, a specialized tree structure used to represent expressions in mathematical or logical form. This is particularly useful for evaluating mathematical expressions, parsing, and compiler design. Understanding how expression trees function and their construction is essential for efficient expression evaluation.
The expression tree is a binary tree with each internal node representing an operand, and each leaf node representing an operator.
For example, the expression (3 + 5) * (2 - 1) can be represented as an expression tree where:
*
/ \
+ -
/ \ / \
3 5 2 1
Expression trees are a fundamental data structure for representing arithmetic and logical expressions in various notations (infix, postfix, and prefix). These trees can represent different types of expressions, depending on the operators, operands, and their organization in the tree structure. Below are the types of expressions that can be represented by expression trees:
Arithmetic expressions involve mathematical operations like addition, subtraction, multiplication, and division, typically with numerical values (constants or variables).
Expression Tree for 3 + 4 * 2
+
/ \
3 *
/ \
4 2
In this example:
Boolean expressions are used in logical operations, such as AND, OR, NOT, and combinations thereof. These expressions often involve Boolean variables or constants (true or false).
Expression Tree for A AND B OR C
OR
/ \
AND C
/ \
A B
In this case:
Relational expressions compare two values and are commonly used in conditional statements. These expressions use relational operators such as =, >, <, >=, <=, and !=.
Expression Tree for A > B AND C < D:
AND
/ \
> <
/ \ / \
A B C D
Here:
Conditional expressions are expressions used in decision-making, such as if-else statements or ternary operators. A common example is the ternary conditional operator (? :)
Expression Tree for x > 10 ? y : z:
?
/ \
> :
/ \ / \
x 10 y zIn this case:
An expression tree can be constructed using infix, prefix, or postfix notations. Let's break down how these are constructed and represented with example:
+
/ \
A *
/ \
B C
In infix notation, operators are placed between operands. This is the most common way of writing arithmetic expressions.
Step 1: Start with the lowest precedence operator (if multiple operators are present).
Step 2: Make this operator the root of the tree.
Step 3: The left subtree is created from the part of the expression to the left of the operator, and the right subtree is created from the part of the expression to the right of the operator.
Step 4: Recursively apply this process to the left and right subexpressions.
Example: A + B * C
In postfix notation, operators are placed after their operands.
Step 1: Start from the left of the postfix expression and push operands onto a stack.
Step 2: When an operator is encountered, pop the required number of operands (2 for binary operators) from the stack, create a new node for the operator, and make the popped operands its children.
Step 3: Push the new operator node back onto the stack.
Step 4: At the end of the expression, the stack will contain a single node, which is the root of the expression tree.
Example: A B C * +
In prefix notation, operators appear before their operands.
Step 1: Start from the right of the prefix expression and push operands onto a stack.
Step 2: When an operator is encountered, pop the required number of operands (2 for binary operators) from the stack, create a new node for the operator, and make the popped operands its children.
Step 3: Push the new operator node back onto the stack.
Step 4: At the end of the expression, the stack will contain a single node, which is the root of the expression tree.
Example: + A * B C
| Example | Notation | Example | Expression Tree |
|---|---|---|---|
 |
Infix | A + B * C | + (root), with left child A and right child * (subtree with B and C as leaves) |
| Postfix | A B C * + | Same as the infix tree, but the construction order follows postfix operations | |
| Prefix | + A * B C | Same as the infix tree, but the construction order follows prefix operations |
Here are the advantages and disadvantages of the expression tree:
Some of the algorithms are commonly used to manipulate and evaluate expression trees:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
// Define a structure for the tree node
struct Node {
char data;
struct Node *left, *right;
};
// Stack structure to hold nodes during tree construction
struct Stack {
int top;
unsigned capacity;
struct Node **array;
};
// Function to create a new tree node
struct Node* newNode(char data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
// Function to create a stack for nodes
struct Stack* createStack(unsigned capacity) {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (struct Node**)malloc(stack->capacity * sizeof(struct Node*));
return stack;
}
// Stack operations
int isFull(struct Stack* stack) { return stack->top == stack->capacity - 1; }
int isEmpty(struct Stack* stack) { return stack->top == -1; }
void push(struct Stack* stack, struct Node* node) {
if (isFull(stack)) return;
stack->array[++stack->top] = node;
}
struct Node* pop(struct Stack* stack) {
if (isEmpty(stack)) return NULL;
return stack->array[stack->top--];
}
// Function to check if a character is an operator
int isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/');
}
// Function to build the expression tree from a postfix expression
struct Node* constructExpressionTree(char* postfix) {
struct Stack* stack = createStack(strlen(postfix));
struct Node *node, *left, *right;
for (int i = 0; postfix[i]; i++) {
// If the character is an operand, create a node and push to stack
if (!isOperator(postfix[i])) {
node = newNode(postfix[i]);
push(stack, node);
} else {
// If the character is an operator, pop two nodes and make them children
right = pop(stack);
left = pop(stack);
node = newNode(postfix[i]);
node->left = left;
node->right = right;
push(stack, node);
}
}
return pop(stack); // The final node will be the root of the tree
}
// Function to perform inorder traversal (infix notation)
void inorder(struct Node* root) {
if (root) {
inorder(root->left);
printf("%c ", root->data);
inorder(root->right);
}
}
// Function to perform preorder traversal (prefix notation)
void preorder(struct Node* root) {
if (root) {
printf("%c ", root->data);
preorder(root->left);
preorder(root->right);
}
}
// Function to perform postorder traversal (postfix notation)
void postorder(struct Node* root) {
if (root) {
postorder(root->left);
postorder(root->right);
printf("%c ", root->data);
}
}
// Main function
int main() {
char postfix[] = "ab+c*d-"; // Example postfix expression: (a + b) * c - d
struct Node* root = constructExpressionTree(postfix);
printf("Infix Expression: ");
inorder(root);
printf("\n");
printf("Prefix Expression: ");
preorder(root);
printf("\n");
printf("Postfix Expression: ");
postorder(root);
printf("\n");
return 0;
}
Output
Infix Expression: a + b * c - d
Prefix Expression: - * + a b c d
Postfix Expression: a b + c * d -In conclusion, an expression tree is a binary tree used to represent mathematical expressions, where leaf nodes are operands and internal nodes are operators. It efficiently supports expression evaluation, respects operator precedence, and simplifies transformations. Expression trees are widely used in compilers, calculators, and computer algebra systems for parsing, evaluating, and optimizing expressions. By using traversals like post-order, expressions can be evaluated or simplified easily.
Yes, expression trees are a key component in symbolic computation systems, allowing for symbolic manipulation and simplification of algebraic expressions.
The time complexity of evaluating an expression tree is O(n), where n is the number of nodes in the tree since each node is visited once during a post-order traversal.
