We can define a binary tree representation T€² for an ordered general tree T as follows (see Figure 8.21):

€¢ For each position p of T, there is an associated position p€² of T€².

€¢ If p is a leaf of T, then p€² in T€² does not have a left child; otherwise the left child of p€² is q€², where q is the first child of p in T.

€¢ If p has a sibling q ordered immediately after it in T, then q€² is the right child of p€² in T; otherwise p€² does not have a right child.

Given such a representation T€² of a general ordered tree T, answer each of the following questions:

a. Is a preorder traversal of T€² equivalent to a preorder traversal of T?

b. Is a postorder traversal of T€² equivalent to a postorder traversal of T?

c. Is an inorder traversal of T€² equivalent to one of the standard traversals of T? If so, which one?

Transcribed Image Text:

D G (b) (a) B.