% (c) 2005 D E Knuth; use and enjoy, but please don't blame me for mistakes... \datethis \def\title{FRAN\c{C}ON} @*Introduction. This short program implements a Fran\c{c}on-inspired bijection between binary trees with Strahler number~$s$ and nested strings with height~$h$, where $2^s-1\le h<2^{s+1}-1$. But it uses a direct method that is complementary to his approach. [Reference: Jean Fran\c{c}on, Sur le nombre de registres n\'ecessaires a l'\'evaluation d'une expression arithm\'etique,'' {\sl R.A.I.R.O. Informatique th\'eorique\/ \bf18} (1984), 355--364.] @d n 17 /* nodes in the tree */ @d nn (n+n) @c #include int d[nn+1]; /* the path, a sequence of $\pm1$s */ int l[n+1],r[n+1]; /* tree links */ int h[nn+1],q[n+1],qm[n+1]; /* heap and queue structures for decision-making */ int serial; /* total number of cases checked */ int count[10]; /* individual counts by Strahler number */ @# @@; @# main() { register int i,j,k,jj,kk,m,p,s; printf("Checking binary trees with %d nodes...\n",n); @; while (1) { @; @; @; @; } done: for (s=1;count[s];s++) printf("Altogether %d cases with Strahler number %d.\n",count[s],s); } @ Nested strings (aka Dyck words) are conveniently generated by Algorithm 7.2.1.6P of {\sl The Art of Computer Programming}. @= for (k=0;k= d[i]=-1; if (d[i-1]<0) d[i-1]=1, i--; else { for (j=i-1,k=nn-2;d[j]>0;j--,k-=2) { d[j]=-1, d[k]=+1; if (j==0) goto done; } d[j]=+1,i=nn-2; } @ @= for (s=j=k=1;k=((1<= int strahler(int x) { register int sl,sr; if (l[x]) sl=strahler(l[x]); else sl=0; if (r[x]) sr=strahler(r[x]); else sr=0; return (sl>sr? sl: sl0|, and to null if |d[p]<0|. The bijection implemented here is of that type. To decide what link should be constructed next, we use a heap-like data structure |h[1]|, |h[2]|, \dots, in which cell $k$ is the parent of cells $2k$ and $2k+1$. The cell elements are pointers to nodes in the tree being built, and the nodes recorded in the heap can be embedded as a subtree of that tree. (In other words, if $h[k]$ and $h[\lfloor k/2\rfloor]$ are both nonzero, they point to nodes of the tree in which the first is a descendant of the second. It might be helpful to imagine a set of pebbles on the tree, with the heap cells recording the positions of those pebbles.) When $h[2k]=0$, meaning that heap cell $2k$ is empty, we also have $h[2k+1]=0$. The basic idea of the algorithm is to attempt to fill the first empty cell $k$ in the heap, by setting the links of the tree node pointed to by $h[k/2]$. The number of elements in the heap is always the partial sum $d[0]+\cdots+d[p]$. If this number is $2^t-1$ or more, the Strahler number of the binary tree is at least~$t$. Conversely, if the Strahler number is~$s$, one can show without difficulty that the partial sum will indeed reach the value $2^s-1$ at some point, with the heap at that time containing the topmost'' complete subtree of size $2^s-1$ embedded in the tree. For validity of this algorithm, we don't really need to choose the first hole in the heap. Any rule for choosing~$k$ would work, provided only that (a)~$k$ is even; (b)~$h[k/2]\ne0$; and (c)~$k\ge 2^t$ implies $d[0]+\cdots+d[p]\ge 2^t-1$. Thus there are many possible bijections, some of which are presumably easier to analyze than others. @ Variable |m| represents the number of nodes in the tree; variable |p| is our position in the nested string; and variable |k| is a lower bound on the location of the least hole in the heap. @= h[1]=m=1, k=2, p=0; while (1) { while (h[k]) k+=2; /* find the smallest hole */ kk=h[k>>1]; /* |kk| is the node pointed to by |k|'s parent */ if (d[++p]>0) h[k]=l[kk]=++m;@+ else l[kk]=0; if (d[++p]>0) h[k+1]=r[kk]=++m;@+ else r[kk]=0; if (h[k]) { if (h[k+1]) continue; kk=k; }@+else if (h[k+1]) kk=k+1; else { h[k>>1]=0, kk=(k>>1)^1, k=kk&-2; if (k==0) break; /* we're done when the heap is empty */ } @; } @ Let the binary representation of |kk| be $(b_t\ldots b_0)_2$. We want to set $h[(b_t\ldots b_1\alpha)_2]\gets h[(b_t\ldots b_0\alpha)_2]$ for all binary strings~$\alpha$. @= j=0,jj=1,q[0]=kk,qm[0]=1; while (j>1)&-qm[j])+(kk&(qm[j]-1))]=h[kk]; if (h[kk+kk]) q[jj]=kk+kk, q[jj+1]=kk+kk+1, qm[jj]=qm[jj+1]=qm[j]<<1, jj+=2; else h[kk]=0; j++; } @* The inverse algorithm. To reverse the process, we simply look at the tree and build the nested string, instead of vice versa. The same heap-oriented logic applies. @d check(s) {@+if (d[++p]!=s) fprintf(stderr,"Rejection at position %d of case %d!\n",p,serial);@+} @= h[1]=1, k=2, p=0; while (1) { while (h[k]) k+=2; /* find the smallest hole */ kk=h[k>>1]; /* |kk| is the node pointed to by |k|'s parent */ if (l[kk]) { h[k]=l[kk];@+check(+1); }@+ else check(-1); if (r[kk]) { h[k+1]=r[kk];@+check(+1); }@+ else check(-1); if (h[k]) { if (h[k+1]) continue; kk=k; }@+else if (h[k+1]) kk=k+1; else { h[k>>1]=0, kk=(k>>1)^1, k=kk&-2; if (k==0) break; /* we're done when the heap is empty */ } @; } @*Index.