TAOCP 2.3.4.5 Exercise 11
Yes.
Exercise 11. [**] [16] Is there any connection between the complete binary tree (5) and the "Dewey decimal notation" for binary trees described in exercise 2.3.1-5?
Verified: yes
Solve time: 46s
Yes. The complete binary tree (5) corresponds directly to the Dewey decimal notation of exercise 2.3.1-5, in the sense that the sequential numbering of the internal nodes encodes the position of each node in the tree unambiguously. In Dewey decimal notation, a node is identified by the sequence of branch numbers leading from the root, which is equivalent to repeatedly applying the parent and child formulas $ \text{parent}(k) = \lfloor k/2 \rfloor $ and $ \text{children}(k) = 2k, 2k+1 $ in the complete binary tree. Each internal node’s number determines its position in the same hierarchical structure used in the Dewey notation.
Therefore, the complete binary tree provides a natural numeric representation that reproduces the Dewey decimal labels: the node numbers encode the path from the root in the same manner as the sequences of integers in the Dewey scheme. The correspondence is one-to-one, and the tree’s sequential structure mirrors the lexicographic ordering of Dewey decimal codes. ∎