Non-Linear Data Structure 533
15.3 TYPES OF BINARY TREE
Strictly binary tree: Fig. 15.4 shows a strictly binary tree. When every no-leaf node in a binary tree is
filled with left and right subtrees, the tree is called a strictly binary tree.
Fig. 15.4 Strictly binary tree
In Fig. 15.4 nodes A, C and D provide two nodes each, whereas Fig. 15.3 is not a strictly binary tree. It
is because nodes C and D have only one son. The binary tree also contains levels. The root of the tree
has level 0 and the level of the other nodes is always greater by one than of their father. As per the
figure, the node H is at level 3 and node E is at level 2. The depth of the binary tree is the highest level
of leaf in the tree.
The node of the binary tree has three fields. The first field represents data and second and third
fields contain information of left and right sons of the node.
Complete binary tree: In a complete binary tree all the nodes have two sons (branches), excluding
the last node. Such a binary tree is shown in Fig. 15.5.
Fig. 15.5 Complete binary tree
With the above structure, we can easily find right and left branches of any node. The left and right
sons will be at positions 2n and 2n+l, respectively. Father of any node will be at position (m/2), where
n and 2 are both integers.
Extended binary tree: The binary tree that is extended with zero (no nodes) or left or right node or
both the nodes is called an extended binary tree or a 2-tree. The extended binary tree is shown in Fig.
15.6.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.