Section 6.2 Trees and Their Representations
523
12. Draw the binary tree corresponding to the left child–right child representation that follows. (1 is the root.)
Left child Right child
2
0
3
4
0
0
5
6
0
0
0
0
1
2
3
4
5
6
13. Write the left child–right child array representation for the binary search tree that is created by processing
the following list of words: “All Gaul is divided into three parts” (see Exercise 43 of Section 5.1). Also
store the name of each node.
14. Write the left child–right child array representation for the binary search tree that is created by processing
the following list of words: “We hold these truths to be self-evident, that all men are created equal” (see
Exercise 43 of Section 5.1). Also store the name of each node.
15. In the following binary tree representation, the left child and parent of each node are given. Draw the
binary tree. (1 is the root.)
Left child
Parent
2
0
4
1
0
1
0
2
0
2
0
3
1
2
3
4
5
6
16. The following represents a tree (not necessarily binary) where, for each node, the leftmost child and the
closest right sibling of that node are given. Draw the tree. (1 is the root.)
Left child Right sibling
2
0
5
3
0
4
8
0
0
6
0
7
0
0
0
0
1
2
3
4
5
6
7
8