HOME

TheInfoList



OR:

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
algebra Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics. Elementary ...
ic and boolean. These trees can represent expressions that contain both unary and binary operators. 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.


Overview

The leaves of a binary expression tree are operands, such as constants or variable names, and the other nodes contain operators. These particular trees happen to be binary, because all of the operations are binary, and although this is the simplest case, it is possible for nodes to have more than two children. It is also possible for a node to have only one child, as is the case with the unary minus operator. An expression tree, ''T'', can be evaluated by applying the operator at the root to the values obtained by recursively evaluating the left and right subtrees.


Traversal

An algebraic expression can be produced from a binary expression tree by recursively producing a parenthesized left expression, then printing out the operator at the root, and finally recursively producing a parenthesized right expression. This general strategy (left, node, right) is known as an
in-order traversal In computer science, tree traversal (also known as tree search and walking the tree) is a form of graph traversal and refers to the process of visiting (e.g. retrieving, updating, or deleting) each node in a tree data structure, exactly once ...
. An alternate traversal strategy is to recursively print out the left subtree, the right subtree, and then the operator. This traversal strategy is generally known as post-order traversal. A third strategy is to print out the operator first and then recursively print out the left and right subtree known as pre-order traversal. These three standard depth-first traversals are representations of the three different expression formats: infix, postfix, and prefix. An infix expression is produced by the inorder traversal, a postfix expression is produced by the post-order traversal, and a prefix expression is produced by the pre-order traversal.


Infix traversal

When an infix expression is printed, an opening and closing parenthesis must be added at the beginning and ending of each expression. As every subtree represents a subexpression, an opening parenthesis is printed at its start and the closing parenthesis is printed after processing all of its children. Pseudocode: Algorithm infix (tree) /*Print the infix expression for an expression tree. Pre : tree is a pointer to an expression tree Post: the infix expression has been printed*/ if (tree not empty) if (tree token is operator) print (open parenthesis) end if infix (tree left subtree) print (tree token) infix (tree right subtree) if (tree token is operator) print (close parenthesis) end if end if end infix


Postfix traversal

The postfix expression is formed by the basic postorder traversal of any binary tree. It does not require parentheses. Pseudocode: Algorithm postfix (tree) /*Print the postfix expression for an expression tree. Pre : tree is a pointer to an expression tree Post: the postfix expression has been printed*/ if (tree not empty) postfix (tree left subtree) postfix (tree right subtree) print (tree token) end if end postfix


Prefix traversal

Pseudocode: Algorithm prefix (tree) /*Print the prefix expression for an expression tree. Pre : tree is a pointer to an expression tree Post: the prefix expression has been printed*/ if (tree not empty) print (tree token) prefix (tree left subtree) prefix (tree right subtree) end if end prefix


Construction of an expression tree

The construction of the tree takes place by reading the postfix expression one symbol at a time. If the symbol is an operand, a one-node tree is created and its pointer is pushed onto a
stack Stack may refer to: Places * Stack Island, an island game reserve in Bass Strait, south-eastern Australia, in Tasmania’s Hunter Island Group * Blue Stack Mountains, in Co. Donegal, Ireland People * Stack (surname) (including a list of people ...
. If the symbol is an operator, the pointers to two trees ''T1'' and ''T2'' are popped from the stack and a new tree whose root is the operator and whose left and right children point to ''T2'' and ''T1'' respectively is formed . A pointer to this new tree is then pushed to the Stack.Mark Allen Weiss,''Data Structures and Algorithm Analysis in C,2nd edition'', Addison Wesley publications


Example

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. 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. 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. Continuing, a '+' is read, and it merges the last two trees. Now, a '*' is read. The last two tree pointers are popped and a new tree is formed with a '*' as the root. Finally, the last symbol is read. The two trees are merged and a pointer to the final tree remains on the stack.


Algebraic expressions

Algebraic expression trees represent expressions that contain
number A number is a mathematical object used to count, measure, and label. The original examples are the natural numbers 1, 2, 3, 4, and so forth. Numbers can be represented in language with number words. More universally, individual number ...
s, variables, and unary and binary operators. Some of the common operators are × (
multiplication Multiplication (often denoted by the Multiplication sign, cross symbol , by the mid-line #Notation and terminology, dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four Elementary arithmetic, elementary Op ...
), ÷ ( division), + (
addition Addition (usually signified by the plus symbol ) is one of the four basic operations of arithmetic, the other three being subtraction, multiplication and division. The addition of two whole numbers results in the total amount or '' sum'' ...
), − ( subtraction), ^ (
exponentiation Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to ...
), and - (
negation In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and false ...
). The operators are contained in the internal nodes of the tree, with the numbers and variables in the leaf nodes. The nodes of binary operators have two child nodes, and the unary operators have one child node.


Boolean expressions

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 \land (
AND or AND may refer to: Logic, grammar, and computing * Conjunction (grammar), connecting two words, phrases, or clauses * Logical conjunction in mathematical logic, notated as "∧", "⋅", "&", or simple juxtaposition * Bitwise AND, a boolea ...
), \lor ( OR), \neg ( NOT).


See also

* Expression (mathematics) * Term (logic) *
Context-free grammar In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form :A\ \to\ \alpha with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be em ...
*
Parse tree A parse tree or parsing tree or derivation tree or concrete syntax tree is an ordered, rooted tree that represents the syntactic structure of a string according to some context-free grammar. The term ''parse tree'' itself is used primarily in co ...
* Abstract syntax tree


References

{{Reflist, refs= Gopal, Arpita. ''Magnifying Data Structures''. PHI Learning, 2010, p. 352. Gopal, Arpita. ''Magnifying Data Structures''. PHI Learning, 2010, p. 353. Richard F. Gilberg & Behrouz A. Forouzan. ''Data Structures: A Pseudocode Approach with C''. Thomson Course Technology, 2005, p. 280. Binary trees Computer algebra