閱讀以下說明和C函數,填補代碼中的空缺(1)~(6),將解答填入答題紙的對應欄內。
【說明】
二叉樹的寬度定義為含有結點數最多的那一層上的結點數。函數GetWidth()用于求二叉樹的寬度。其思路是根據樹的高度設置一個數組counter[],counter[i]存放第i層上的結點數,并按照層次順序來遍歷二叉樹中的結點,在此過程中可獲得每個結點的層次值,最后從counter[]中取出最大的元素就是樹的寬度。
按照層次順序遍歷二叉樹的實現方法是借助一個隊列,按訪問結點的先后順序來記錄結點,離根結點越近的結點越先進入隊列,具體處理過程為:先令根結點及其層次號(為1)進入初始為空的隊列,然后在隊列非空的情況下,取出隊頭所指示的結點及其層次號,然后將該結點的左予樹根結點及層次號入隊列(若左子樹存在),其次將該結點的右子樹根結點及層次號入隊列(若右子樹存在),然后再取隊頭,重復該過程直至完成遍歷。
設二叉樹采用二叉鏈表存儲,結點類型定義如下:
typedef struct BTNode {
TElemType data;
struct BTNode *left, *right;
} BTNode, *BiTree;
隊列元素的類型定義如下:
typedef struct {
BTNode *ptr;
int LevelNumber;
} QElemType;
GetWidth()函數中用到的函數原型如下所述,隊列的類型名為QUEUE:
【C函數】
int GetWidth(BiTree root)
{
QUEUE Q;
QElemType a, b;
int width, height=GetHeight(root);
int i, *counter=(int *) calloc (height+1, sizeof(int));
if ( (1) ) return -1; /* 申請空間失敗 */
if ( !root ) return 0; /* 空樹的寬度為0 */
if ( (2) ) return -1; /* 初始化隊列失敗時返回 */
a.ptr=root; a.LevelNumber=1;
if (!EnQueue ( &Q, a)) return -1; /* 元素入隊列操作失敗時返回 */
while (!isEmpty (Q)) {
if( (3) )return-1; /* 出隊列操作失敗時返回*/
counter[b.LevelNumber]++; /* 對層號為b.LevelNumber的結點計數 */
if(b.ptr->left){ */ 若左子樹存在,則左子樹根結點及其層次號入隊 */
a.ptr=b.ptr->left;
a.LevelNumber= (4) ;
if ( !EnQueue (&Q, a)) return -1;
}
if(b.ptr->right){ /* 若右子樹存在,則右子樹根結點及其層次號入隊 */
a.ptr = b.ptr->right;
a.LeveINumber= (5) ;
if ( !EnQueue (&Q, a)) return -1;
}
}
width=counter [1] ;
for (i=1; i< height +1; i++) /* 求counter[]中的最大值 */
if ( (6) ) width=counter[i];
free(counter);
return width;
}