TAOCP 2.3 Exercise 22

Section 2.3: Trees

Exercise 22. ▶ [**] [21] Standard European paper sizes A0, A1, A2, ..., An, ... are rectangles whose sides are in the ratio $\sqrt{2}$ to 1 and whose areas are $2^{-n}$ square meters. Therefore if we cut a sheet of An paper in half, we get two sheets of A(n + 1) paper. Use this principle to design a graphic representation of binary trees, and illustrate your idea by drawing the representation of 2.3.1-(1) below.

It is important to acquire a good understanding of the properties of binary trees before making further investigations of trees, since general trees are usually represented in terms of some equivalent binary tree inside a computer.

We have defined a binary tree as a finite set of nodes that either is empty, or consists of a root together with two binary trees. This definition suggests a natural way to represent binary trees within a computer: We can have two links, LLINK and RLINK, within each node, and a link variable T that is a "pointer to the tree." If the tree is empty, T = \Lambda; otherwise T is the address of the root node of the tree, and LLINK(T), RLINK(T) are pointers to the left and right subtrees of the root, respectively. These rules recursively define the memory representation of any binary tree; for example,

This simple and natural memory representation accounts for the special importance of binary tree structures. We will see in Section 2.3.2 that general trees can conveniently be represented as binary trees. Moreover, many trees that arise in applications are themselves inherently binary, so binary trees are of interest in their own right.

Verified: no
Solve time: 27s

We represent binary trees graphically using standard European paper sizes A0, A1, A2, ..., so that each node occupies a rectangle whose width-to-height ratio is $\sqrt{2}:1$, and the area of a node at depth $n$ is $2^{-n}$ relative to the root. Cutting a rectangle in half vertically produces two child rectangles of the next smaller size, corresponding to the left and right subtrees. Recursively applying this principle, the root occupies an A0 rectangle, its children occupy A1 rectangles, their children occupy A2 rectangles, and so on. This construction ensures that the subtree of each node fits precisely within the area of that node, maintaining proportionality and allowing clear visualization of the binary tree structure.

For the tree 2.3.1-(1), the root occupies an A0 rectangle, the left and right subtrees occupy A1 rectangles, and their respective subtrees occupy A2 rectangles, recursively. Each rectangle is subdivided according to whether the corresponding node has a left or right child, producing a compact and proportional graphic representation. This method directly illustrates the recursive nature of binary trees and their correspondence to halving operations on rectangular areas.