Knuth apologized for having no time to give his program a better user
interface, and hoped someone would write an interactive “app” for playing with its trees and
graphs. Here is a first piece of one — Alice the ant’s walk, and the four conjugates it finds.
Theorem. Every family of 2n+2 cyclically equivalent ternary
trees contains exactly four skew ternary trees.
Put a bud in every empty slot of a ternary tree. The root node and the root bud
have rank 0, and the left, middle, and right children of a node of rank r have ranks
r−1, r, and r+1. The tree is skew if no node has negative rank.
Figure 1The tree with its buds
RankBud number — its mate carries the same number with an overlineUnmatched bud
Figure 2Alice’s walk
Stacked buds
Figure 3The four conjugates
Hang the tree from each of the four unmatched buds in turn, and you get
T, T+, T++, and T+++, with
T++++ = T. Click one to move to that tree — the shape stays
the same and only the bud it hangs from changes, so the buds are renumbered from the new root.