资源描述：
《mark allen weiss 数据结构与算法分析 课后习题答案4》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Chapter4:Trees4.1(a)AO.(b)GO,HO,IO,LO,MO,andKO.4.2FornodeBO:(a)AO.(b)DOandEO.(c)CO.(d)1.(e)3.4.34.4.4ThereareNOnodes.Eachnodehastwopointers,sothereare2NOpointers.Eachnodebuttheroothasoneincomingpointerfromitsparent,whichaccountsforNO-1pointers.TherestareNULL.O4.5Proofisbyinduction.T
2、hetheoremistriviallytrueforHO=0.AssumetrueforHO=1,2,...,kO.AtreeofheightkO+1canhavetwosubtreesofheightatmostkO.Thesecanhaveatmost2kO+1-1nodeseachbytheinductionhypothesis.These2kO+2-2nodesplustherootprovethetheoremforheightkO+1andhenceforallheights.4.6Thiscanbeshownbyinduction.Altern
3、atively,letNO=numberofnodes,FO=numberoffullnodes,LO=numberofleaves,andHO=numberofhalfnodes(nodeswithonechild).Clearly,NO=FO+HO+LO.Further,2FO+HO=NO-1(seeExercise4.4).SubtractingyieldsLO-FO=1.4.7Thiscanbeshownbyinduction.Inatreewithnonodes,thesumiszero,andinaone-nodetree,therootisale
4、afatdepthzero,sotheclaimistrue.SupposethetheoremistrueforalltreeswithatmostkOnodes.ConsideranytreewithkO+1nodes.SuchatreeconsistsofaniOnodeleftsubtreeandakO-iOnoderightsubtree.Bytheinductivehypothesis,thesumfortheleftsubtreeleavesisatmostonewithrespecttothelefttreeroot.Becausealllea
5、vesareonedeeperwithrespecttotheoriginaltreethanwithrespecttothesubtree,thesumisatmost¤12withrespecttotheroot.Similarlogicimpliesthatthesumforleavesintherightsubtreeisatmost¤12,provingthetheorem.Theequalityistrueifandonlyiftherearenonodeswithonechild.Ifthereisanodewithonechild,theequ
6、alitycannotbetruebecauseaddingthesecondchildwouldincreasethesumtohigherthan1.Ifnonodeshaveonechild,thenwecan®ndandremovetwosiblingleaves,creatinganewtree.Itiseasytoseethatthisnewtreehasthesamesumastheold.Applyingthissteprepeatedly,wearriveatasinglenode,whosesumis1.Thustheoriginaltre
7、ehadsum1.4.8(a)-**ab+cde.(b)((a*b)*(c+d))-e.(c)ab*cd+*e-.-14-4.93414162625959774.11Thisproblemisnotmuchdifferentfromthelinkedlistcursorimplementation.Wemaintainanarrayofrecordsconsistingofanelement®eld,andtwointegers,leftandright.Thefreelistcanbemaintainedbylinkingthroughtheleft®eld
8、.Itiseasytowritethe
