Page 198 - DCAP407_DATA_STRUCTURE

Unit 10: Trees

In the above representation, 0 indicates the null link. The major advantage of array representation of
trees is that it helps in getting direct access to any node. However, the drawback is that it is necessary to
fix the maximum depth of the tree since the array size has already been decided. If the array size is quite
larger than the depth of the tree, then it is considered to be memory wastage. If the array size is lesser
than the depth of the tree, then it is not possible to represent some parts of the tree.

10.4 Application of Trees
Trees are used in operating systems, compiler design, and searching. Expression tree is an example of
general structure known as parse tree, which is a central data structure in compiler design. Parse trees
are not binary but are comparatively simple extensions of expression trees. Another remarkable
application of trees is in designing of computer games such as Nim, Tic-tac-toe, Chess, Kalah, Checkers,
and so on.
A decision tree is a binary tree where a node represents a decision and edges represent the outcome of
the decision. A decision tree is thus a powerful method for classification and prediction, and facilitates
decision making in sequential decision problems.
Let us discuss in detail the various applications of trees.
10.4.1 Expression Trees
Expression trees are special kind of binary trees. An expression tree provides a method to translate
executable code into data. This translation of data is very useful to modify or transform the code before
executing it. The leaves of an expression tree are operands such as constants or variable names, and the
other nodes contain operators. This specific tree is binary because all the operations are binary, and it is
not possible for nodes to have more than two children.
To evaluate an expression tree, we recursively evaluate the left and right sub-trees and then apply the
operator at the root. We can produce an infix expression by recursively producing a parenthesized left
expression, and then printing out the operator at the root, and later recursively producing a
parenthesized right expression. This approach (left, node, right) is known as an inorder traversal.
An alternate traversal strategy is to recursively print out the left sub-tree, the right sub-tree, and then
the operator. This traversal approach (left, right, node) is known as a postorder traversal.
Figure 10.21 shows an example of an expression tree. In this example, the left sub-tree evaluates to a +
(b * c) and the right sub-tree evaluates to ((d *e) + f)*g. The entire tree therefore represents (a + (b*c)) +
(((d * e) + f)* g).

Figure 10.21: Expression Tree for (a + b * c) + ((d * e + f ) * g)

LOVELY PROFESSIONAL UNIVERSITY 191