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

254 BINARY TREES [CHAP. 10

(c) END points to the location of the last node ofT; hence END=15.

We finally obtain the sequential representation ofTin Fig. 10-23.

Fig. 10-23

10.4. Consider the treesT 1 ,T 2 ,T 3 in Fig. 10-24. Identify those which represent the same:

(a) rooted tree; (b) ordered rooted tree; (c) binary tree.

(a) They all represent the same rooted tree, that is,Ais the root with children (immediate successors)BandC, and

Chas the single childD.

(b) HereT 1 andT 2 are the same ordered rooted tree butT 3 is different. Specifically,Bis the first child ofAinT 1 and

T 2 but the second child ofAinT 3.

(c) They all represent different binary trees. Specifically,T 1 andT 2 are different since we distinguish between left

and right successors even when there is only one successor (which is not true for ordered rooted trees). That is,

Dis a left successor ofCinT 1 but a right successor ofCinT 2.

Fig. 10-24

10.5.A binary treeThas nine nodes. Draw a picture ofTif the preorder and inorder traversal ofTyield the

following sequences of nodes:

Preorder: GBQAC P DE R

Inorder: QBC AGP E DR

The treeTis drawn from its rootRdownward as follows.

(a) The root ofTis obtained by choosing the first node in its preorder. ThusGis the root ofT.

(b) The left child of nodeGis obtained as follows. First use the inorder ofTto find the nodes in the left subtreeT 1

ofG. ThusT 1 consists of the nodesQ, B, C, A, which are to the left ofGin the inorder ofT. Then the left child

ofGis obtained by choosing the first node (root) in the preorder ofT 1 which appears in the preorder ofT. Thus

Bis the left child ofG.

(c) Similarly, the right subtreeT 2 ofGconsists of the nodesP,E,D,R; andPis the root ofT 2 , that is,Pis the right

child ofG.

Repeating the above process with each new node, we finally obtain the required treeTin Fig. 10-25(a).

10.6. Consider the algebraic expressionE=( 2 x+y)( 5 a−b)^3.

(a) Draw the corresponding 2-tree. (b) UseTto writeEin Polish prefix form.

(a) Use an arrow (↑) for exponentiation, an asterisk (*) for multiplication, and a slash (/) for division to obtain the

tree in Fig. 10-25(b).