Page 210 - DCAP407_DATA_STRUCTURE

Unit 11: Introduction to Binary Trees

d and e. A binary tree in which its non-leaf nodes possess exactly two child nodes represents a strictly
binary tree.
Extended Binary Tree

A binary tree is called an extended binary tree when every node in the tree either has 0 or 2 sub nodes
(child nodes). The nodes with two child nodes are called internal nodes and nodes without child nodes
are called external nodes. The extended binary tree is also called a 2-tree. The nodes in the binary tree
possessing only one child node can be extended with one more child node. The extended binary tree
plays a very important role in implementing algebraic expressions. The algebraic expressions are
represented by operands and operators. Hence, the left and right child nodes represent the operands
and parent node represents the operator.

Consider figure 11.6 that depicts a binary tree with a single child node. The
binary tree with single child node is initial phase of designing the binary tree
which can be made a complete binary tree by extending the nodes.

Figure 11.6: Binary Tree with Single Child Node

In the figure 11.6, the parent nodes b and c have only one child each, node d and e respectively. The
node e also has single child node f. By adding another child node to the parent nodes b, c and e, we can
obtain an extended binary tree.
Figure 11.7 depicts an extended binary tree.

Figure 11.7: Extended Binary Tree

In the figure 11.7, the extended binary nodes are represented by a rectangular box. The parent nodes b, c
and e are provided with two child nodes by extending the nodes.

LOVELY PROFESSIONAL UNIVERSITY 203