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

　　[題目分析] 由定義結點的平衡因子bf等於結點的左子樹高度與右子樹高度之差設計一遍歷算法在遍歷結點時求結點的左子樹和右子樹的高度然後得到結點的平衡因子

　　int Height(BiTree bt)//求二叉樹bt的深度
　　{int hlhr;
　　if (bt==null) return();
　　else {hl=Height(bt>lchild); hr=Height(bt>rchild);
　　if(hl>hr) return (hl+); else return(hr+);
　　}  }// Height
　　void  Balance(BiTree bt)
　　//計算二叉樹bt各結點的平衡因子
　　{if (bt)
　　{Balance(bt>lchild); //後序遍歷左子樹
　　Balance(bt>rchild); //後序遍歷右子樹
　　hl=Height(bt>lchild); hr=Height(bt>rchild);//求左右子樹的高度
　　bt>bf=hlhr; //結點的平衡因子bf
　　}   }//算法結束

　　[題目分析]本題應采用層次遍歷方式若樹不空則二叉樹根結點入隊然後當隊列不空且隊列長不超過n重復如下操作出隊若出隊元素不為空則記住其下標且將其左右子女入隊列若出隊元素為空當作虛結點也將其虛子女入隊列為節省空間就用樹T的順序存儲結構A[n]作隊列隊頭指針front隊尾指針rear元素最大下標last

　　void  Traverse(BiTree bt int n)
　　// 求二叉樹bt的順序存儲結構A[n]下標超過n報錯給出實際的最大下標
　　{BiTree A[] p;
　　if(bt!=null)
　　{int front=rear=last=; A[]=bt;
　　while(front<=rear)
　　{p=A[++front]; if(p) last=front; // 出隊;用last記住最後一個結點的下標
　　rear=*front;//計算結點（包括虛結點）左子女下標
　　if (p)       //二叉樹的實際結點
　　{if(rear>n)   printf(%c結點無左子女); else A[rear]=p>lchild;
　　if(rear+>n) printf(%c結點無右子女); else A[rear+]=p>rchild;
　　}
　　else //p是虛結點
　　{ if(rear<=n) A[rear]=null; if(rear+<=n) A[rear+]=null; }
　　}// while(front<=rear)
　　printf(實際的最大下標是%dlast);
　　}//if(bt!=null)   }//Traverse

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

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