Home | | **Object Oriented Programming and Data Structures** | Implementation of a Binary Tree with an expression tree

What is a Binary Tree? EA binary tree is a tree in which no node can have more than two children. Figure 4.11 shows that a binary tree consists of a root and two subtrees, TL and TR, both of which could possibly be empty.xplain the implementation of a Binary Tree with an expression tree

**What is a Binary Tree? Explain
the implementation of a Binary Tree with an expression tree**

A binary
tree is a tree in which no node can have more than two children. Figure 4.11
shows that a binary tree consists of a root and two subtrees, *TL* and *TR*, both of which could possibly be empty. A property of a binary
tree that is sometimes important is that the depth of an average binary tree is
considerably smaller than *N*. An
analysis shows that the average depth is *O*(√*N*), and that for a special type of
binary tree, namely the* binary search
tree, *the average* *value of the
depth is *O*(log*N*). Unfortunately, the depth can be as large as *N* − 1, as the example in Figure 4.12
shows.

ch1.r 3

ch2.r 2

ch3.r 4

book 10

syl.r 1

fall 2

syl.r 5

spr 6

syl.r 2

sum 3

cop3530
12

course 13

junk 6

mark 30

junk 8

alex 9

work 1

grades 3

prog1.r 4

prog2.r 1

fall 9

prog2.r 2

prog1.r 7

grades 9

fall 19

cop3212
29

course 30
bill 32

/usr 72

**Implementation**

Because a
binary tree node has at most two children, we can keep direct links to them.
The declaration of tree nodes is similar in structure to that for doubly linked
lists, in that a node is a structure consisting of the element information plus
two pointers (left and right) to other nodes(Figure 4.13). We could draw the
binary trees using the rectangular boxes that are customary for linked lists,
but trees are generally drawn as circles connected by lines, because they are
actually graphs. We also do not explicitly draw nullptr links when referring to
trees, because every binary tree with *N*
nodes would require *N* + 1 nullptr
links. Binary trees have many important uses not associated with searching. One
of the principal uses of binary trees is in the area of compiler design, which
we will now explore.

**Example: Expression Trees**

Figure
4.14 shows an example of an **expression
tree**. The leaves of an expression tree are **operands**, such as constants or variable names, and the other nodes
contain** operators**. This** **particular tree happens to be binary,
because all the operators 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. We can evaluate an expression tree, *T*, by applying the operator at the root
to the values struct BinaryNode

{

Object
element; // The data in the node

BinaryNode
*left; // Left child

BinaryNode
*right; // Right child

};

obtained
by recursively evaluating the left and right subtrees. In our example, the left
subtree evaluates to a + (b * c) and the right subtree evaluates to ((d * e) +
f) * g. The entire tree therefore represents (a + (b * c)) + (((d * e) + f) *
g). We can produce an (overly parenthesized) infix expression 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 **inorder traversal**; it is easy to remember because of the type of
expression it produces. An alternate traversal strategy is to recursively print
out the left subtree, the right subtree, and then the operator. If we apply
this strategy to our tree above, the output is a b c * + d e * f + g * +, which
is easily seen to be the postfix representation. This traversal strategy is
generally known as a *postorder*
traversal. A third traversal strategy is to print out the operator first and then
recursively print out the left and right subtrees. The resulting expression, +
+ a * b c * + * d e f g, is the less useful *prefix*
notation, and the traversal strategy is a *preorder*
traversal

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Object Oriented Programming and Data Structure : Non-Linear Data Structures : Implementation of a Binary Tree with an expression tree |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.