CHAP. 10] BINARY TREES 237
10.3Complete and Extended Binary Trees
This section considers two special kinds of binary trees.Complete Binary Trees
Consider any binary treeT. Each node ofTcan have at most two children. Accordingly, one can show that
levelrofTcan have at most 2rnodes. The treeTis said to becompleteif all its levels, except possibly the last,
have the maximum number of possible nodes, and if all the nodes at the last level appear as far left as possible.
Thus there is a unique complete treeTnwith exactlynnodes (where we ignore the contents of the nodes). The
complete treeT 26 with 26 nodes appears in Fig. 10-2.
Fig. 10-2 Complete treeT 26ThenodesofthecompletebinarytreeT 26 inFig.10-2havebeenpurposelylabeledbytheintegers1, 2 ,...,26,
from left to right, generation by generation. With this labeling, one can easily determine the children and parent
of any nodeKin any complete treeTn. Specifically, the left and right children of the nodeKare, respectively,
2 ∗Kand 2∗K+1, and the parent ofKis the node[K/ 2 ]. For example, the children of node 9 are the nodes
18 and 19, and its parent is the node[ 9 / 2 ]=4. The depthdnof the complete treeTnwithnnodes is given by
dn=log 2 n+ 1 This is a relatively small number. For example, if the complete treeTnhasn=1 000 000 nodes, then its depth
dn=21.
Extended Binary Trees: 2-Trees
A binary tree treeTis said to be a2-treeor anextended binary treeif each nodeNhas either 0 or 2 children.
In such a case, the nodes with two children are calledinternal nodes, and the nodes with 0 children are called
external nodes. Sometimes the nodes are distinguished in diagrams by using circles for internal nodes and squares
for external nodes.
The term “extended binary tree” comes from the following operation. Consider any binary treeT, such as
the tree in Fig. 10-3(a). ThenTmay be “converted” into a 2-tree by replacing each empty subtree by a new node,
as pictured in Fig. 10-3(b). Observe that the new tree is, indeed, a 2-tree. Furthermore, the nodes in the original
treeTare now the internal nodes in the extended tree, and the new nodes are the external nodes in the extended
tree. We note that if a 2-tree hasninternal nodes, then it will haven+1 external nodes.