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

　　．[題目分析]由孩子兄弟鏈表表示的樹求高度的遞歸模型是若樹為空高度為零若第一子女為空高度為和兄弟子樹的高度的大者否則高度為第一子女樹高度加和兄弟子樹高度的大者其非遞歸算法使用隊列逐層遍歷樹取得樹的高度

　　int Height(CSTree bt)     //遞歸求以孩子兄弟鏈表表示的樹的深度
　　{int hchs;
　　if (bt==null) return ();
　　else if (!bt>firstchild) return (+height(bt>nextsibling);//子女空查兄弟的深度
　　else  // 結點既有第一子女又有兄弟高度取子女高度+和兄弟子樹高度的大者
　　{hc=height(bt>firstchild) //第一子女樹高
　　hs=height(bt>nextsibling)//兄弟樹高
　　if(hc+>hs)return(hc+);  else return (hs);
　　}
　　}//結束height
　　int height(CSTree t)     //非遞歸遍歷求以孩子兄弟鏈表表示的樹的深度
　　{if(t==null)  return();
　　else{int front=rear=;  //frontrear是隊頭隊尾元素的指針
　　int last=h=;      //last指向樹中同層結點中最後一個結點h是樹的高度
　　Q[rear]=t;           //Q是以樹中結點為元素的隊列
　　while(front<=last)
　　{t=Q[front++];       //隊頭出列
　　while(t!=null)      //層次遍歷
　　{if (t>firstchild) Q[++rear]=t>firstchild; //第一子女入隊
　　t=t>nextsibling; //同層兄弟指針後移
　　}
　　if(front>last)      //本層結束深度加（初始深度為）
　　{h++;last=rear;} //last再移到指向當前層最右一個結點
　　}//while(front<=last)
　　}//else
　　}//Height

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

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