搜索
226200811()JournalofShandongUniversityofTechnology(NaturalScienceEdition)Vol.22No.6Nov.2008:2008208226:(19872),.:1672-6197(2008)06-0108-03,(,255049):,.,,,,,.:;;;:TP311.12:AAgraphicalgorithmofHuffmantreeSUNXue2chen,LIXin2jie(SchoolofScience,ShandongUniversityofTechnology,Zibo255049,China)Abstract:Huffmantreeisoftheshortestlengthamongasetoftreeswithweights,whichisdif2ficulttoexpressingraphicbecauseofitsnonlinearstructure.Inordertofittheneedsoftypeset2tingandobservetheHuffmantreemoredirectly,wehopetodesignanalgorithmthatmakesHuffmantreeeasytobeobserved.ThealgorithmwasbuiltonthetraditionalHuffmancodingal2gorithmandbasedontheworkspaceofHuffmancoding,whichcanestablishtheHuffmantreecorrespondingtotheHuffmancodeswehavegot.Andthenodesofthetreewegotthroughthisalgorithmareingoodorderandarrangement.Besides,nodesandconnectionsbetweennodesdonotoverlapeachother.Keywords:Huffmancode;graphic;algorithmsdesign;datastructure,,,.1952,(Huffman)[122],,.,,.1,,,,,.[1,3],.,.,1.weightlchildrchildparent10042004300531256341,,,..,n2n-1,2n-1,,,.,,,,2.(a)(b),(c),22,,:,,,.,3,C():weightlchildrchildparentidp3typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;//doubleid;//Pointp;//}HTnode,3HuffmanTree;Point:typedefstruct{doublex;//doubley;//}Point;:1),id,1,2,3,.2),id=id2log2idid,id[1,2),id,,(),id.3)2idp.x,.4).5)log2id,,,,h.6).7),(C):HuffmanDrawing(HuffmanTree&HT,intn){//step1HT[23n-1].id=1;for(i=23n-1;in;i--){HT[HT[i].lchild].id=23HT[i].id;HT[HT[i].rchild].id=23HT[i].id+1;}//step2for(i=n;i0;i--)HT[i].id=HT[i].id/pow(2,log(HT[i].id)/log(2));//step3for(i=1;in+1;i++){selectmin(HT,n,min);9016,:HT[min].p.x=(width-n3l)/2+i3l;}//step4for(i=n+1;i23n;i++){HT[i].p.x=(HT[HT[i].lchild].p.x+HT[HT[i].rchild].p.x)/2;}//step5for(i=n+1;i23n;i++){HT[i].p.y=(log(HT[i].id)/log(2))3h+h0;}for(i=n;i0;i--){HT[i].p.y=HT[HT[i].parent].p.y+h;}//step6DrawTree(HT,n);}intselectmin(HuffmanTreeHT,intn,int&m){intj;for(j=1;jn;j++){m=HT[j].idHT[j+1].id?j+1:j;HT[m].id=3.0;}returnm;}DrawTree(HuffmanTreeHT,intn){for(j=23n-1;j0;j++)Circle(HT[j].p,r);TextOut(HT[j].p,symbol,weight);if(HT[j].lchild){Line(HT[j].p,HT[HT[j].lchild].p);Line(HT[j].p,HT[HT[j].rchild].p);}}3,O(6n-3)[4],Selectmin(),O(6n-3),n,.326,.,VC++6.0,26,4.426,,,.4,,,,.,,,,,,,.,.:[1],.(C)[M].:,1997.[2],,.[M].:,2007.[3],,,.[M].:,2001.[4]CormenTH,LeisersonCE,RivestRL.[M].2..:,2006.011()2008