Found some Scheme code that I wrote when I was reading Concrete Mathematics
The Stern–Brocot tree was discovered independently by Moritz Stern (1858) and Achille Brocot (1861). Stern was a German number theorist; Brocot was a French clockmaker who used the Stern–Brocot tree to design systems of gears with a gear ratio close to some desired value by finding a ratio of smooth numbers near that value.
(text below from Concrete Mathematics)
The idea is to start with the two fractions (0/1, 1/0) and then to repeat the following opeation as many times as desired:
Insert (m + m')/(n + n') between two adjacent fractions m/n and m'/n'
The new fraction (m + m')/(n + n') is called the _mediant_ of m/n and m'/n'. For example, the first step gives us one new entry between 0/1 and 1/0:
0/1, 1/1, 1/0
and the next step gives two more
0/1, 1/2, 1/1, 2/1, 1/0
The next gives four more,
0/1, 1/3, 1/2, 2/3, 1/1, 3/2, 2/1, 3/1, 1/0
The entire array can be regarded as an infinite binary tree structure whose top levels look like this:
1 1 0
— - - - - — - - - - —
0 1 1
/ \
/ \
/ \
/ \
1 / \ 2
— —
2 1
/ \ / \
/ \ / \
/ \ / \
1 2 3 3
— — — —
3 3 2 1
/ \ / \ / \ / \
1 2 3 3 4 5 5 4
— — — — — — — —
4 5 5 4 3 3 2 1We can, in fact, regard the Stern-Brocot tree as a number system for representing rational numbers, because each positive, reduced fraction occurs exactly once. Let's use the letters L and R to stand for going down to the left or right branch as we proceed from the root of the tree to a particular fraction; then a string of L's and R's uniquely identifies a place in the tree. For example, LRRL means that we go left from 1/1 down to 1/2, then right to 2/3, then right to 3/4, then left to 5/7. The fraction 1/1 corresponds to the empty string, let's agree to call it I.
Graham, Knuth, Patashnik, Concrete Mathematics, Addison Wesley, 2nd ed. pp 115-123