knuth打印出了建树的过程，自己给一些数据试验一下应该能找到程序的脉络。这个算法可以用来做最优二叉排序树
的建立。这道题只用了前面的combin函数。
#include <cstdio>
#include <iostream>
using namespace std;

const int size = 64000;
int w[size]; /* node weights */
int l[size],r[size]; /* left and right children */
//辅助数组，仅仅为了列印方便 
int d[size]; /* depth */
int q[size]; /* working region */
int v[size]; /* number of node in working region */
//辅助数组，仅仅为了列印方便
int t; /* current size of working region */
//标记当前未处理的节点个数 
int m; /* current node */


int ans;
void combine(int t);
void mark(int k, int p);
void build(int b);
int main()
{
    int i, j, k, n;
    for(; ;)
    {
        scanf("%d", &n);
        if(!n) break;
        --n;
           
        for(j = 0; j <= n; j++)
        {
            scanf("%d", &w[j]);
            l[j] = r[j] = -1;
        }
        if(!n)
        {
            printf("0\n");
            continue;
        } 
        m=n;
        t=1;
        ans = 0;
        q[0]=1000000000; /* infinity */
        q[1]=w[0]; v[1]=0;
        for(k=1;k<=n;k++) 
        {
            while(q[t-1] <= w[k]) //从左往右扫描，第一次遇到a, b, c且a > b, c > a，则将a, b合并 
            combine(t);
            t++; 
            q[t]=w[k]; 
            v[t]=k;
            for (j=1;j<=t;j++) printf("%d ",q[j]); printf("\n");
        }
        while(t > 1) 
           combine(t);
        cout << ans << endl;
       /* mark(v[1],0);
        t=0; m=2*n;
        build(1);*/
    }    
}    

void combine(int k)
{
  int j,d,x;
  m++; l[m]=v[k-1]; r[m]=v[k]; w[m]=x=q[k-1]+q[k];//注意合并成为一棵树，新节点放在w数组的后面 
  printf(" node %d(%d)=%d(%d)+%d(%d)\n",m,x,l[m],w[l[m]],r[m],w[r[m]]);//原程序中的列印 
  ans += x;
  t--;
  for (j=k;j<=t;j++) q[j]=q[j+1],v[j]=v[j+1];
  for (j=k-2;q[j]<x;j--) q[j+1]=q[j],v[j+1]=v[j];
  q[j+1]=x; v[j+1]=m;
 for (d=1;d<=t;d++) printf("%d ",q[d]);
  printf("\n");
  while (j>0 && q[j-1]<=x) {
    d=t-j; combine(j); j=t-d;
  }
}


void mark(int k, int p)//int k; /* node */int p; /* starting depth */
{
  //printf(" node %d(%d) has depth %d\n",k,w[k],p);
  d[k]=p;
  if (l[k]>=0) mark(l[k],p+1);
  if (r[k]>=0) mark(r[k],p+1);
}



/*
@ The |build| subroutine rebuilds a tree from the depth table,
by doing a depth-first search according a slick idea by Bob Tarjan.
It creates a tree rooted at node~|m| having leftmost leaf~|t|.

@<Sub...@>=*/
void build(int b)
{
  int j=m;
  if (d[t]==b) l[j]=t++;
  else {
    m--; l[j]=m; build(b+1);
  }
  if (d[t]==b) r[j]=t++;
  else {
    m--; r[j]=m; build(b+1);
  }
 // printf(" node %d = %d + %d\n", j,l[j],r[j]);
}
  

• Re:knuth的源代码 (123) rujialiu 2006-08-15 17:03:27
• 一时间看不明白！ (2838) bmexue 2006-10-13 01:12:44