资源描述：
《《数据结构与算法分析》(C++第二版)【美】Clifford A.Shaffer著 课后习题答案 二.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、《数据结构与算法分析》（C++第二版）【美】CliffordA.Shaffer著课后习题答案二5BinaryTrees5.1Consideranon-fullbinarytree.Bydefinition,thistreemusthavesomeinternalnodeXwithonlyonenon-emptychild.IfwemodifythetreetoremoveX,replacingitwithitschild,themodifiedtreewillhaveahigherfractionofno
2、n-emptynodessinceonenon-emptynodeandoneemptynodehavebeenremoved.5.2Useasthebasecasethetreeofoneleafnode.Thenumberofdegree-2nodesis0,andthenumberofleavesis1.Thus,thetheoremholds.Fortheinductionhypothesis,assumethetheoremistrueforanytreewithn−1nodes.Forthei
3、nductionstep,consideratreeTwithnnodes.Removefromthetreeanyleafnode,andcalltheresultingtreeT.Bytheinductionhypothesis,Thasonemoreleafnodethanithasnodesofdegree2.Now,restoretheleafnodethatwasremovedtoformT.Therearetwopossiblecases.(1)Ifthisleafnodeistheonly
4、childofitsparentinT,thenthenumberofnodesofdegree2hasnotchanged,norhasthenumberofleafnodes.Thus,thetheoremholds.(2)IfthisleafnodeisthechildofanodeinTwithdegree2,thenthatnodehasdegree1inT.Thus,byrestoringtheleafnodeweareaddingonenewleafnodeandonenewnodeofde
5、gree2.Thus,thetheoremholds.Bymathematicalinduction,thetheoremiscorrect.32335.3BaseCase:Forthetreeofoneleafnode,I=0,E=0,n=0,sothetheoremholds.InductionHypothesis:Thetheoremholdsforthefullbinarytreecontainingninternalnodes.InductionStep:Takeanarbitrarytree(
6、callitT)ofninternalnodes.SelectsomeinternalnodexfromTthathastwoleaves,andremovethosetwoleaves.CalltheresultingtreeT’.TreeT’isfullandhasn−1internalnodes,sobytheInductionHypothesisE=I+2(n−1).Callthedepthofnodexasd.Restorethetwochildrenofx,eachatleveld+1.Weh
7、avenowaddeddtoIsincexisnowonceagainaninternalnode.Wehavenowadded2(d+1)−d=d+2toEsinceweaddedthetwoleafnodes,butlostthecontributionofxtoE.Thus,ifbeforetheadditionwehadE=I+2(n−1)(bytheinductionhypothesis),thenaftertheadditionwehaveE+d=I+d+2+2(n−1)orE=I+2nwhi
8、chiscorrect.Thus,bytheprincipleofmathematicalinduction,thetheoremiscorrect.5.4(a)templatevoidinorder(BinNode*subroot){if(subroot==NULL)return;//Empty,donothingpreorder(subroot->left());visit(subroot
