最佳二叉搜索树t(i,j 包含关键码key+1,key+2,…,key为内 部结点(0≤i≤j≤n 以key为根 结点的权为(q,p1+1q+1 ■左子树包含key+1,…,keyx1 根为r( c(i,k-1) 1 开销为c(,,即∑n+D)+∑g ■右子树包含keyk+,keyk+ ack,刀)已求出 权的总和为W(i,j= C(,j) P+1+…+p+q+q+1+…+q w(i,j)+ min(c(i, k-1)+C(k, D) 北真大张陪曲写 有,轴即叠究 物啦 写●有:即当亮 01234 姓上2, 开销30 S71 白宁 白宁 北京大学值歌张写所有即究 cN+1][N+1] 1]intw[N+1N+1]) for(int i=O; i<=n; i ++) 3 for(intj=0小j<=nj++)//初始化 B SRD 3 RH 需出=0 IRB RI for(i-0; i<-n; i++)I willi]- blip for(int j-i+1j<-n:j++)/)求出权和wijl 花费 wlilll-wliI[j-1+all+bll for(intj=1j<n:j++){∥确定一个结点的 BestBST6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 31 最佳二叉搜索树t(i，j) „ 包含关键码keyi+1，keyi+2，…，keyj 为内 部结点(0≤i≤j≤n) „ 结点的权为(qi ，pi+1， qi+1，…，pj ，qj )， „ 根为r(i，j) „ 开销为C(i，j)，即 „ 权的总和为W(i，j) = pi+1+…+pj +qi +qi+1+…+qj 1 (1 1) j j x x xx xi xi p ql =+ = ∑ ∑ + + ′ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 32 „ 以keyk为根 „ 左子树包含keyi+1，…，keyk-1 „ C(i， k-1) „ 右子树包含keyk+l，keyk+2，…，keyj „ C(k，j)已求出 „ C(i，j) = W(i，j)+ (C(i，k-1)+C(k，j)) i k j min < ≤ 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 33 j i 0 1 2 3 4 0 1 2 3 4 0 1 2 2 2 0 2 2 3 0 3 3 0 4 0 r(i ,j) j i 0 1 2 3 4 0 1 2 3 4 0 10 28 43 57 0 12 27 40 0 9 19 0 6 0 C(i ,j) j i 0 1 2 3 4 0 1 2 3 4 5 10 18 21 28 4 12 18 22 3 9 3 3 6 1 W(i ,j) 第 B 一 步 花费 总权 1 5 4 10 10 D 5 4 3 12 12 F 4 3 2 9 9 H 3 2 1 6 6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 34 1 B 5 5 4 3 5 D 3 1 5 4 第 二 步 开销 总权 30 18 28 18 5 D 4 4 3 2 4 F 2 5 4 3 27 18 30 18 D B F D 4 F 3 3 2 1 3 1 4 3 2 19 13 22 13 H F H 第 三 步 花费 总权 1 B 5 5 4 4 D 5 1 5 4 24 F 3 2 4 3 2 B D F 43 24 1 F 3 5 1 2 D 5 4 B 52 24 5 D 4 4 4 3 F 4 1 4 3 41 22 H 2 1 3 2 1 D F H 40 22 3 H 4 5 4 1 D 3 2 F 49 24 第 1 5 4 3 51 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 35 第 四 步 花费 总权 1 B 5 4 3 F 5 1 5 4 68 28 H 2 1 4 3 B D F 57 28 3 5 1 D 5 4 3 D 3 2 1 H 4 5 3 1 3 2 D F H 1 5 4 B 62 28 4 F 3 2 1 5 4 B H 71 28 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 36 void OptimalBST(int a[], int b[], int n, int c[N+1][N+1], int r[N+1][N+1], int w[N+1][N+1]) { for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) {// 初始化 c[i][j]=0; r[i][j]=0; w[i][j]=0; } for (i = 0; i <=n; i++) { w[i][i] = b[i]; for(int j=i+1;j<=n;j++) //求出权和w[i.j] w[i][j]=w[i][j-1]+a[j]+b[j]; } for(int j=1;j<=n;j++) { //确定一个结点的BestBST c[j-1][j]=w[j-1][j]; r[j-1][j]=j; }