第5章貪婪法-考研驛站

淘 第五婪貪婪法引背包問單源最短路徑問最小花費(fèi)生成樹問霍夫曼編碼問1江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -1淘 貪婪法引—二三貪婪法的例子_2江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -2淘 幣兌付問貨幣兌付問題：用最少的貨幣張數(shù)支付集合Pp1,p2,pnn張面pi的貨幣，1i出納員需支付的現(xiàn)金為A，從P中選取一個最小的子集使 pi

∑pi=用向量Xx1x2xnS中所選取的貨幣，使pixi

pi出納員支付的現(xiàn)金必須滿足n使得：dmin

∑xipi=3江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -3淘 貨幣兌付問題（續(xù)解向量：問題中n個元素的具體取值所構(gòu)成的解空間：問題中n個元素的各種不同取值組合所構(gòu)全目標(biāo)函數(shù)：問題求解所要達(dá)到的目標(biāo)可行解：滿足約束方程的向最優(yōu)解：使目標(biāo)函數(shù)達(dá)極值的向4江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -4淘 婪法的設(shè)計思5江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -5淘 不斷地從問n個元素中選取一個最優(yōu)的元素的取值，作為向量中的一個分量，使其既滿足約束方程，又使目標(biāo)函數(shù)取極值最快，當(dāng)n個元素的取均求取之后，解向量就成為完整的6江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -6淘 greedy(A,{solution=for(i=1;i<n;i++)x=ifsolution=}return}7江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -7淘 適于用貪婪法求解的條貪婪選擇性質(zhì)：所求問題的列局部最優(yōu)的例1010元、105元、101元、105102角、101角的貨幣中兌付578P={p1,p2,p60順序表示向量Xx1x2x60表示支付給第一步挑出S1={p1}的貨幣集合 Y1=(1,0問題簡化為在P1={p2,p60中挑選貨幣、付47元8角，在以后的步驟中，可以用同樣的方法進(jìn)選，并能得到問題的全8江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -8淘 適于用貪婪法求解的條件（續(xù)付給客戶的貨幣集合的最優(yōu)解是Sn={p1,p2,p3,p4,p5,p11,p21,p22,p31,p41,p51第一步所簡化了的子問Sn-1={p2,p3,p4,p5,p11,p21,p22,p31,p41,p51 Sn-1∪{p1}=所以，出納員付錢問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)9江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -9淘 婪法的例子_貨郎擔(dān)問貨郎擔(dān)問題：5個城市123453725423235625312345372542323562531

江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -10淘 貪婪法的例子_貨郎擔(dān)問題（續(xù)1234537254232356253只選擇一個城市作為出發(fā)城市，所需時間是O(n2)n個城市都可以作為出發(fā)城市，所需時間是O(n3)1出發(fā)的1234537254232356253江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -11淘 背包問—背包問題二思想方法三數(shù)據(jù)結(jié)構(gòu)四算法描述五算法分析江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -12淘 包問載重量為M的背包，重量為wi、價值為pi 1in，把物體裝滿背包，使背包內(nèi)的物體價值最大物體可以分割的背包問題，及物體不可分割的背包問題，把后者稱為0/1背包問題江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -13淘 想方解向量：Xx1x2xnxi：物體被裝入背包的部分，0xi1xi=0：物體沒被裝入背包；xi1：物體被全部n約束方程 ∑wixi=目標(biāo)函數(shù)

d=max選取價值重量比最大的物體裝入，既使目標(biāo)函數(shù)的值增加最快，又使背包載重量的消耗較慢江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -14淘 據(jù)結(jié)typedefstructfloatp;floatw;floatv;} instance[n

//n個物體的//n個物體的//n個物體的價值floatx[n //n個物體裝入背包的江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -15淘 法描floatknapsack_greedy(floatM,OBJECTinstance[floatx[],int intfloatm,p=for(i=0;i<n;i++){

instance[i].v=instance[i].p/instance[i].w;x[i]=0;m=

江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -16淘 算法描述（續(xù)for(i=0;i<n;i++)if(instance[i].w<=13.x[i]= m-=instance[i

p+=instance[ielsex[i]=m/instance[ip+=x[i]*instance[i return23.江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -17淘 法分題的最優(yōu)解證明：設(shè)解向量為Xx1x2xn，分兩種情況X中存j，1j<n，使x1x2xj110xj1，xj+1xn0，有n

wixi=M1=

假定，算法的最優(yōu)解是Yy1y2,yn)，并且n∑wiyi=M2=

江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -18淘 算法分析（續(xù)XY，必存k1i<kxiyikxk≠xk<

，這時，有兩因為yk≤ 所 xk<根據(jù)算法的執(zhí)

xk+1==xn=則

M1<>

與(1),(2) ，所以X= M=∑wixi≥∑wixi>∑ yk+1,,

不會全 江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -19淘 算法分析（續(xù)令ykΔyk=xk并使yk+1,

相應(yīng)得到

Z=(z1,z2,,zn1ik時有：ziyiik時有kin并且

yk<zk=xkzi<yin(zk-yk)wk ∑(yi-zi)wi=江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -20淘 算法分析（續(xù)令δ=pk -y)

pk+1

) pn

z)

((z

y)

- ) -z)

)=

δ0Z是一個新的最優(yōu)δ0ZY同為最在此兩種情況下，都用ZY，并且對所有1ik有：zi= ，而對k+1in，有：zi≠對向Z重復(fù)上述步驟，最終必有：對所有的1in，zi=xi因此，X是最優(yōu)江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -21淘 單源最短路徑問—解最短路徑的狄斯奎諾（Dijkstra）算法二狄斯奎諾算法的描述三江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -22淘 解最短路徑的狄斯奎諾（Dijkstra）算江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -23淘 有向賦權(quán)G=<V,E>，求源頂u到其它所有頂江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -24淘 記號約

(uv)的長：頂u到頂vp(x)：從u到頂x的最短路徑點(diǎn)V劃分為集SS中的頂點(diǎn)u的距離T中的頂點(diǎn)u的距離未江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -25淘 狄斯奎諾算法的實現(xiàn)步驟（續(xù)實現(xiàn)步①S={u},T=V–{uxT，若(u,xEdu,xcu,x，p(x否則，du,x∞，p(x-1tT，使得du,tmindu,x|xT④S=ST，T=T–{tT，算法結(jié)束；否t相鄰接的所x，如果du,xdu,t否則，令du,xdu,tct,x，p(xt江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -26淘 例求圖中頂點(diǎn)a到其它所頂點(diǎn)的距

7h0鄰接矩陣如下 h00a1b4cd40b2ce90c3d6e3f0a1b4cd40b2ce90c3d6e3fg40dg70eh10f2eh50g1fh3江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -27淘 例子（續(xù)

求圖中頂點(diǎn)a到其它所 4頂點(diǎn)的距離的

7 St1a1441b2343c349674d49676f5877g688e799h8江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -28淘 例子（續(xù)頂點(diǎn)的路

ab7ab cbadaefcbafcbagcbahefcbacbadaefcbafcbagcbahefcba江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -29淘 斯奎諾算法江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -30淘 typedefstructadj_listintfloatstructadj_list}

//鄰接表結(jié)點(diǎn)的//鄰接頂點(diǎn)的//鄰接頂點(diǎn)與該頂點(diǎn)的距//下一個鄰接//鄰接表頭//頂點(diǎn)到源頂點(diǎn)//頂點(diǎn)到源頂點(diǎn) 方頂點(diǎn)的為真,頂點(diǎn)S中,否則,不在江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -31淘 #defineMAX_FLOT_NUM //最大的浮voiddijkstra(NODEnode[],intn,intu,floatd[],intp[{ inti,j,BOOL*s=newBOOL[nNODEfor(i=0;i<n;i++)d[i]=p[i]=-

//s[i]=

江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -32淘 算法描述（步驟if(!(pnode=while(pnode)

//源頂點(diǎn)與其它//相鄰//預(yù)置與源頂點(diǎn)相鄰

d[pnode->v_num]=pnode-p[pnode->v_num]=

//的頂點(diǎn)距

pnode=pnode- d[u]= s[u]= //開始時,集合S//頂點(diǎn)江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -33淘 算法描述（步驟for(i=1;i<n;i++)temp=for(j=0;j<n;if(!s[j]&&d[j]<temp){

t=T中尋找距//最近的

t= temp=d[j}if(t==u)break;s[t]=TRUE;

//找不到,跳出//否則t并入集合江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -34淘 算法描述（步驟

pnode=node[twhile(pnode)if(!s[pnode->v_num]

//更新與t相鄰接//頂點(diǎn)到u的距

d[pnode->v_num]>d[t]+pnode->len){d[pnode->v_num]=d[t]+pnode->len;p[pnode->v_num]=t; pnode=pnode- delete

狄斯奎諾算法的實現(xiàn)步驟（續(xù) 江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -35淘 斯奎諾算法的分時間復(fù)雜O(n2算法正確性證江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -36淘 最小花費(fèi)生成樹問克魯斯卡爾（Kluskal）算法三普里姆（Prim）算法江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -37淘 最小花費(fèi)生成樹引江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -38淘 定義G<V,E>GV’,E’>G’VV，則G’G的生成例如(a是無向完全(bc(de)是它生成子定義無向G的生成子T是樹，則TG例如(b)不是(a的生成樹，而圖(c)d(e)都(a)的生 江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -39淘 若連通GvE>，TG的生成樹。則生成樹T如下性質(zhì)1：T是不含簡單回路的連2：T中的每一對頂uv，恰好有一條uv的基本通3|V|=n，|E|=mm=n–性質(zhì)4：在T中的任何兩個不相鄰接的頂點(diǎn)之條邊，則得到T中唯一的一條基本江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -40淘 魯斯卡爾（Kluskal）算克魯斯卡爾算法的思想方克魯斯卡爾算克魯斯卡爾算江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -41淘 克魯斯卡爾算法的思想方思想方法T；會使T構(gòu)成回路把它加入森林中（或者是把森林中某兩在這兩種情況下，都把它從邊集中重復(fù)這個n1條邊都放到森林森林中所有的樹就被連接成一棵樹T，它就是所要求取的最小花費(fèi)生成江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -42淘 實現(xiàn)按權(quán)的非降順序排E③把每個頂點(diǎn)都初始化為樹的根e(uv)E中權(quán)最小的邊，EEefind(ufind(v)，則執(zhí)union(uv)操作T=T|T|n1算江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -43淘 下圖表示克魯斯卡爾算1 4

1

江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -44淘 數(shù)據(jù)typedefstruct //邊的數(shù)據(jù)////與邊關(guān)聯(lián)的頂//與邊關(guān)聯(lián)的頂}typedefstructnodestruct

//頂點(diǎn)的數(shù)據(jù)結(jié)//指向父親

//結(jié)點(diǎn)的//頂點(diǎn)E[m+1E[m+1],T[n//圖的邊集及V[n//圖的頂點(diǎn)集江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -45淘 算法描述（voidkruskal(NODEV[],EDGEE[EDGET[],intn,int{inti,j,EDGENODE*u,

for(i=0;i<n;i++)

//用邊集構(gòu)成//用頂點(diǎn)作為樹的根結(jié)V[i].rank=

V[i].p=

//構(gòu)成森江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -46淘 2）算法描述（i=j=while((i<n-1)&&(m>0)e=delete_min(E,u=find(&V[e.uv=find(&V[e.vif(u!=v)union(u,T[j++]= 21.

//從堆中取下//檢索該邊兩頂點(diǎn)所 樹//兩頂點(diǎn)不在同一棵//合并成一//該邊置于生成樹江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -47淘 克魯斯卡爾算法的分6m條邊構(gòu)成最小12delete_min操作執(zhí)m次，花find操作2munion操作最多執(zhí)m最多花O(mlog*n)O(m)時間對完全圖，mn(n–1)/2，花費(fèi)的時間O(n2對平面m=O(n)，花費(fèi)的工作單最小生成樹邊集所需空其余工作單元為江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -48淘 算法的正確性證G是無向連通圖，T’是最小花費(fèi)T是由克魯斯卡爾算法所G中的頂點(diǎn)T中的頂點(diǎn)，也T’中的頂點(diǎn)若G的頂點(diǎn)n|T|=|T’|=n–1用歸納法證T=江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -49淘 算法的正確性證明（續(xù)e1G中權(quán)最小的邊，根據(jù)克魯斯卡爾算法，有e1若e1T’T’G的最小花費(fèi)和e1關(guān)聯(lián)的頂點(diǎn)必是T’中的兩個不相把e1T’T’構(gòu)成唯一的假定回路e1,ea1,e1是這條回路中令TT∪e1eaieaiea1,,eak的任意一T’’仍然是的生T’’的權(quán)小于或等于T’的權(quán)T’’的權(quán)小T’的權(quán)T’G的最小花費(fèi)生成樹的邊集，所e1∈T'T’’的權(quán)等T’的權(quán)T’’也是的最小花邊集e1∈T，用新T’來標(biāo)記在這兩種情況下，都有e1 江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -50淘 算法的正確性證明（續(xù)

TT’中前k條權(quán)最小的令ek+1Tk1條權(quán)最小的邊ek+1∈Tek+1和ek+1關(guān)聯(lián)的頂點(diǎn)也是T’中的兩個不相ek+1T’，將T’構(gòu)成唯一的一假定回路是ek+1,ea1 在ea1,,eam中，至少有一條eaieaiT，否則，T將存在ek+1是在 之后找到的第一條不會使e1,,ek構(gòu)成回路的權(quán)

e1,,ek所以ek+1的權(quán)小于于或等于eai的權(quán)令TT'∪ek+1eaiT仍然G的生成的權(quán)小于或等于T’的權(quán)。同①，有ek+1∈T' 江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -51淘 里姆（Prim）算普里姆算法的普里姆算法的實普里姆算法的分江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -52淘 普里姆算法的思設(shè)頂點(diǎn)集V0,1,n1}，與頂i,j相關(guān)的邊ei,j，權(quán)c[i][jT是最小花費(fèi)生成樹的邊兩個頂點(diǎn)集合S開始時T=，S={0}，N=V–iS,jN，并ci][j]最小ijS=S{j}，N=N–{j，TT∪ei,j}重復(fù)上述步N為空，或找n–1條邊江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -53淘 普里姆算法的執(zhí)行步①T=，S={0}，N=V–②N為空，算法結(jié)束；否則，轉(zhuǎn)iS，jN，cij最小iSSj，NNj}TT∪ei,j，轉(zhuǎn)2江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -54淘 下圖表示普里姆算法的工作過程

5 1

江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -55淘 普里姆算法的iS，jN，c[i][j]最小ij邊界點(diǎn)：若存在邊ei,jiS，jNj為邊邊界點(diǎn)是由集N轉(zhuǎn)移到集S的候近鄰j是邊界點(diǎn)S中至少有一ij相鄰接Sj相鄰接、且cij最小的頂i，稱為頂j的近鄰neig[n]：登記頂jwn 登記頂j與近鄰初始化時，置neig[j]= w[j]=c[0][jwj]最小j，再neig[j]j的近則邊

T中的把j加入S，更新N中頂點(diǎn)j的neig[j]和w[j 江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -56淘 數(shù)據(jù)//圖的鄰接//最小花費(fèi)生j的近j與近鄰相關(guān)聯(lián)江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -57淘 3）算法描述（步驟voidprim(floatc[][],intn,EDGET[],int inti,j,k,BOOL*s=newBOOL[nint*neig=newint[nfloatmin,*w=newfloat[ns[0]=for(i=1;i<n;i++)w[i]=c[0][ineig[i]=s[i]=

//S=江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -58淘 算法描述（步驟k=for(i=1;i<n;i++)u=min=for(j=1;j<n;if(!s[j]&&w[j]<min)u= min=w[j if(u==0)T[k].u=neig[u T[k].v= T[k++].key= s[u]=

江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -59淘 算法描述（步驟

forj=1;j<n;j //更新N中頂點(diǎn)if(!s[j]&&c[u][j]<w[j])w[j]=c[u][j

neig[j]=

delete35.

delete delete江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -60淘 普里姆算法的時間復(fù)雜性：O(n2算法的正確性設(shè)普里姆算法所產(chǎn)生的最小花費(fèi)生成樹的邊集是無向賦權(quán)圖的最小花費(fèi)生成樹的邊集是T’，eijT前論點(diǎn)e(i,jT時，iSjN,cijS’=S{j}，T’=T{e}，GS’,T’>江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -61淘 普里姆算法的分析（續(xù)SS{j}，T’’=Te}，G’S’,T’’>G是樹eS中的一個頂點(diǎn)關(guān)聯(lián)T后不會G’構(gòu)成回路，且GG的最小花費(fèi)生成樹的子樹：若eT’，上述結(jié)論成立eT’e關(guān)聯(lián)的頂T’中兩個不相鄰接T’{e}將包含e是回路的一條e=(i,j)iS,j則回路中必存在另一條邊e’=(x,y)，xS,y江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -62淘 普里姆算法的分析（續(xù)e是回路的一條e=(i,j)iS,j則回路中必存在另一條邊e’=(x,y)，xS,y按算法的選擇，e的權(quán)小于或等于e’的 T’’=T{eeT的權(quán)小于或等T’

T’’的權(quán)小T’的權(quán)T’是最小花費(fèi)生成樹所以，eT的權(quán)等T’的權(quán)，這T’來標(biāo)在這兩種情況e江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -63淘 霍夫曼編碼問二霍夫曼編碼的實現(xiàn)江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -64淘 霍夫曼編碼思想代碼，以達(dá)到壓縮文件長度的目的前綴假設(shè)a1a2a3an是長度n的字符串a(chǎn)1a2a3(k=1,2,…n-1)為字符串a(chǎn)1a2a3an的長度n江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -65淘 —個字符的編碼是另—個字程中可能產(chǎn)生例a,b,c,d編碼abcde字符abcd的碼01011110111將作010111101 被譯成江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -66淘 前綴碼和最優(yōu)二叉二元前綴碼假設(shè)字符串集合A{s1s2,,sm}。若對任意siAsjA，ijsis不互為前綴，則稱A為前綴碼。特別的，若(i=1,2,…,m)中只出01兩種符號，A為二元前綴碼江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -67淘 前綴碼和最優(yōu)二叉二元前綴碼和二叉樹一個具有n個字符編碼的二元前綴碼，可以表示成一棵有n片葉子的二叉樹，每片葉子代表一個字符，而把字符的編碼看成是從根沿著表示該字符的葉子的路徑，0表示左子樹方向路徑、1表示右子樹方向路徑。例：字a,b,c,d,e編碼為：對應(yīng)的二

111 a 江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -68淘 前綴碼和最優(yōu)二叉霍夫曼編碼對字符c1,進(jìn)行編碼pi為文件中字ci出現(xiàn)的頻率l(i)為對應(yīng)二叉樹中相應(yīng)于ci的葉子結(jié)點(diǎn)nW(T)pil(cin最小的二叉T，其相應(yīng)的前綴碼便是一個最佳編碼，江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -69淘 二叉霍夫曼樹的定定義5.6若二叉T的每個分支都有2個兒子T叉正定義5.7若二叉正則Tn片葉ci，分別帶ni12n，則稱nW(T)pil(ci

pi

T的權(quán)。在帶權(quán)pinci的所有二叉正則樹中(5.5.1)最小的樹，稱為帶權(quán)pi的最優(yōu)二叉樹。最優(yōu)二叉樹也稱霍夫曼樹江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -70淘 二叉5.霍夫曼樹的構(gòu)5.6p1p2p的最優(yōu)二叉樹中T，使得帶p1和p2的兩片葉子是兄弟證明： T0帶權(quán)p1p2pn的最優(yōu)二叉樹，cx T0中路徑最長的兩片葉子，它們分別帶權(quán)px和 l(c1

l(c2

l(c1 l(c2 l(cx) l(cy l(cx) l(cy江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -71淘 二叉證明：px py l(cx)l(ci l(cy)l(ci i1,把帶權(quán)的葉c1、c2分別與帶權(quán)的得到新樹T，有：

cx和cy及權(quán)互換W(T)W(T0)p1l(cx)p2l(cy)pxl(c1)pyl(c2)pxl(cx)pyl(cy)p1l(c1)p2l(c2l(cx)(p1px)l(cy)(p2py)l(c1)(pxp1)l(c2)(pyl(cx(1px)l(cy)(p2py)l(c1)(p1px)l(c2)(p2py(p1px)(l(cx)l(c1))(p2py)(l(cy)l(c2T0是最優(yōu)二叉樹，所以，T也是最優(yōu)二叉樹，且c1和c2兄江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -72淘 二叉定理5.7T1是帶權(quán)p1p2p3,pn的最優(yōu)二叉p1p2p3pn，在T1中，使p1p2的葉子產(chǎn)生兩片分別帶權(quán)p1p2的葉子，則得到帶權(quán)p1,p2,pn的最優(yōu)二叉樹T證明因為T1是帶權(quán)p1p2 p3,,pn的最優(yōu)二叉樹而T是T1p1p2p1p2葉子得到的帶權(quán)p1,p2,pn的二叉令lp1p2p1p2lp1和lp2分別為帶權(quán)p1p2的葉子到根結(jié)點(diǎn)路徑l(p1)l(p2)l(p1p2)江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -73淘 二叉 W(T)W(T1)p1設(shè)T是帶權(quán)p1p2,pn的最優(yōu)二叉樹，據(jù)定5.6，可得p1p2的葉子c1和c2在T'中刪去c1和c2，使其父結(jié)點(diǎn)的權(quán)為p1p2，得到樹T1'。 W(T')W(T1')p1p2因為T1是最優(yōu)二叉樹，所以W(T1')W而W(T)W(T')W(T1)p1p2(W(T1')p1p2W(T1)W(T1'因為T'是最優(yōu)二叉樹，所以，T是最優(yōu)二叉樹 江南大學(xué)833c語言考研資料由快樂考研驛站整理編寫 -74淘 二叉例：有8個字符