Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

252 BINARY TREES [CHAP. 10

Remark:A binary treeTis not a special case of a general treeT. They are two different objects. The two basic
differences follow:

(1) A binary treeT′may be empty, but a general treeTis nonempty.

(2) Suppose a nodeNhas only one child. Then the child is distinguished as a left child or right child in a binary

treeT′, but no such distinction exists in a general treeT.

The second difference is illustrated by the treesT 1 andT 2 in Fig. 10-20(b). Specifically, as binary trees,T 1 andT 2
are distinct trees, sinceBis the left child ofAin the treeT 1 butBis the right child ofAin the treeT 2. On the other
hand, there is no difference between the treesT 1 andT 2 as general trees.

Forest

Aforest Fis defined to be an ordered collection of zero or more distinct general trees. Clearly, if we delete
the rootRfrom a general treeT, then we obtain the forestFconsisting of the subtrees ofR(which may be empty).
Conversely, ifFis a forest, then we may adjoin a nodeRtoFto form a general treeTwhereRis the root ofTand
the subtrees ofRconsist of the original trees inF.

General Trees and Binary Trees

SupposeTis a general tree. Then we may assign a unique binary treeT′toTas follows. First of all, the
nodes of the binary treeT′will be the same as the nodes of the general treeT, and the root ofT′will be the root
ofT. LetNbe an arbitrary node of the binary treeT′. Then the left child ofNinT′will be the first child of the
nodeNin the general treeTand the right child ofNinT′will be the next sibling ofNin the general treeT. This
correspondence is illustrated in Problem 10.16.

SolvedProblems

BINARY TREES

10.1. SupposeTis the binary tree stored in memory as in Fig. 10-21. Draw the diagram ofT.

Fig. 10-21

The treeTis drawn from its rootRdownward as follows:

(a) The rootRis obtained from the value of the pointer ROOT. Note that ROOT=5. Hence INFO[ 5 ]=60 is the

rootRofT.

(b) The left child ofRis obtained from the left pointer field ofR. Note that LEFT[ 5 ]=2. Hence INFO[ 2 ]=30 is

the left child ofR.

(c) The right child ofRis obtained from the right pointer field ofR. Note that RIGHT[ 5 ]=6. Hence INFO[ 6 ]= 70

is the right child ofR.

We can now draw the top part of the tree, then, repeating the process with each new node, we finally obtain the entire

treeTin Fig. 10-22(a)