數據結構考研分類復習真題 第六章 答案 (五)[37]

　　[題目分析]上題是打印從根結點到某結點p的路徑上所有祖先結點本題是打印由根結點到葉子結點的所有路徑只要在上題基礎上把q是否等於p的判斷改為q是否是葉子結點即可其語句段如下

　　if(q>lchild==null&&q>rchild==null) //q為葉子結點
　　{printf(從根結點到p結點的路徑為\n);
　　for(i=;i<=top;i++) printf(s[i]>data);//輸出從根到葉子路徑上葉子q的所有祖先
　　printf(q>data); }

　　[題目分析]因為後序遍歷棧中保留當前結點的祖先的信息用一變量保存棧的最高棧頂指針每當退棧時棧頂指針高於保存最高棧頂指針的值時則將該棧倒入輔助棧中輔助棧始終保存最長路徑長度上的結點直至後序遍歷完畢則輔助棧中內容即為所求

　　void LongestPath(BiTree bt)//求二叉樹中的第一條最長路徑長度
　　{BiTree p=btl[]s[]; //l s是棧元素是二叉樹結點指針l中保留當前最長路徑中的結點
　　int itop=tag[]longest=;
　　while(p || top>)
　　{ while(p) {s[++top]=ptag[top]=; p=p>Lc;} //沿左分枝向下
　　if(tag[top]==)    //當前結點的右分枝已遍歷
　　{if(!s[top]>Lc && !s[top]>Rc)  //只有到葉子結點時才查看路徑長度
　　if(top>longest) {for(i=;i<=top;i++) l[i]=s[i]; longest=top; top;}
　　//保留當前最長路徑到l棧記住最高棧頂指針退棧
　　}
　　else if(top>) {tag[top]=; p=s[top]Rc;}   //沿右子分枝向下
　　}//while(p!=null||top>)
　　}//結束LongestPath

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23715.html