📑 Table of Contents▼

A binary expression tree is a specific kind of a binary tree used to represent expressions. Two common types of expressions that a binary expression tree can represent are algebraic[1] and boolean. These trees can represent expressions that contain both unary and binary operators.[1]

Like any binary tree, each node of a binary expression tree has zero, one, or two children. This restricted structure simplifies the processing of expression trees.

Construction of an expression tree

edit

Example

edit

The input in postfix notation is: a b + c d e + * * Since the first two symbols are operands, one-node trees are created and pointers to them are pushed onto a stack. For convenience the stack will grow from left to right.

Stack growing from left to right

The next symbol is a '+'. It pops the two pointers to the trees, a new tree is formed, and a pointer to it is pushed onto the stack.

Formation of a new tree

Next, c, d, and e are read. A one-node tree is created for each and a pointer to the corresponding tree is pushed onto the stack.

Creating a one-node tree

Continuing, a '+' is read, and it merges the last two trees.

Merging two trees

Now, a '*' is read. The last two tree pointers are popped and a new tree is formed with a '*' as the root.

Forming a new tree with a root

Finally, the last symbol is read. The two trees are merged and a pointer to the final tree remains on the stack.[2]

Steps to construct an expression tree a b + c d e + * *

Algebraic expressions

edit
Binary algebraic expression tree equivalent to ((5 + z) / -8) * (4 ^ 2)

Algebraic expression trees represent expressions that contain numbers, variables, and unary and binary operators. Some of the common operators are × (multiplication), ÷ (division), + (addition), − (subtraction), ^ (exponentiation), and - (negation). The operators are contained in the internal nodes of the tree, with the numbers and variables in the leaf nodes.[1] The nodes of binary operators have two child nodes, and the unary operators have one child node.

Boolean expressions

edit
Binary boolean expression tree equivalent to ((true false) false) (true false))

Boolean expressions are represented very similarly to algebraic expressions, the only difference being the specific values and operators used. Boolean expressions use true and false as constant values, and the operators include (AND), (OR), (NOT).

See also

edit

References

edit
  1. ^ a b c Bruno R. Preiss (1998). "Expression Trees". Archived from the original on January 19, 2017. Retrieved December 20, 2010.
  2. ^ Gopal, Arpita. Magnifying Data Structures. PHI Learning, 2010, p. 353.

📚 Artikel Terkait di Wikipedia

Binary tree

In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child

Tree traversal

blue). Post-order traversal can be useful to get postfix expression of a binary expression tree. Recursively traverse the current node's left subtree. Visit

Random binary tree

probability theory, a random binary tree is a binary tree selected at random from some probability distribution on binary trees. Different distributions have

Binary logarithm

combinatorics: Every binary tree with n leaves has height at least log2 n, with equality when n is a power of two and the tree is a complete binary tree. Relatedly

Binary heap

binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap

Tree contraction

evaluate an expression given as a binary tree (this problem also known as binary expression tree), consider that: An arithmetic expression is a tree where the

Tree (abstract data type)

single straight line (called edge or link between two adjacent nodes). Binary trees are a commonly used type, which constrain the number of children for

Stern–Brocot tree

In number theory, the Stern–Brocot tree is an infinite complete binary tree whose vertices correspond one-for-one to the positive rational numbers, whose