閱讀以下說明和C 函數(shù),將應填入 (n) 處的字句寫在答題紙的對應欄內(nèi)。
【說明】
已知某二叉樹的非葉子結點都有兩個孩子結點,現(xiàn)將該二叉樹存儲在結構數(shù)組 Ht中。結點結構及數(shù)組Ht的定義如下:
#define MAXLEAFNUM 30
struct node{
char ch; /*當前結點表示的字符,對于非葉子結點,此域不用*/
char *pstr; /*當前結點的編碼指針,非葉子結點不用*/
int parent; /*當前結點的父結點,為0時表示無父結點*/
int lchild,rchild;
/*當前結點的左、右孩子結點,為0時表示無對應的孩子結點*/
};
struct node Ht[2 * MAXLEAFNUM]; /*數(shù)組元素Ht[0]不用*/
該二叉樹的n個葉子結點存儲在下標為1~n的Ht數(shù)組元素中。例如,某二叉樹如圖3-1所示,其存儲結構如圖3-2所示,其中,與葉子結點a對應的數(shù)組元素下標為1,a 的父結點存儲在 Ht[5],表示為 Ht[1].parent=5。Ht[7].parent=0 表示 7 號結點是樹根,Ht[7].lchild=3、Ht[7].rchild=6 分別表示 7 號結點的左孩子是 3號結點、右孩子是 6 號結點。
如果用“0”或“1”分別標識二叉樹的左分支和右分支(如圖 3-1 所示),從根結點開始到葉子結點為止,按所經(jīng)過分支的次序將相應標識依次排列,可得到一個 0、1序列,稱之為對應葉子結點的編碼。例如,圖3-1中a、b、c、d的編碼分別是100、101、0、11。
函數(shù)LeafCode(Ht[],n)的功能是:求解存儲在Ht中的二叉樹中所有葉子結點(n個)的編碼,葉子結點存儲在Ht[1]~Ht[n]中,求出的編碼存儲區(qū)由對應的數(shù)組元素pstr域指示。
函數(shù)LeafCode從葉子到根逆向求葉子結點的編碼。例如,對圖3-1中葉子結點a求編碼的過程如圖3-3所示。
typedef enum Status {ERROR, OK} Status;
【函數(shù)】
Status LeafCode(struct node Ht[], int n)
{
int pc, pf; /*pc用于指出樹中的結點,pf則指出pc所對應結點的父結點*/
int i,start;
char tstr[31] = {‘\0’}; /*臨時存儲給定葉子結點的編碼,從高下標開始存入*/
for(i=1;(1) ; i++) { /*對所有葉子結點求編碼,i表示葉結點在HT數(shù)組中的下標*/
start = 29;
pc = i; pf = Ht[i].parent;
while (pf != (2) ) { /*沒有到達樹根時,繼續(xù)求編碼*/
if ( (3) .lchild == pc ) /*pc所表示的結點是其父結點的左孩子*/
tstr[--start] = ‘0’;
else
tstr[--start] = ‘1’;
pc = (4) ; pf = Ht[pf].parent; /*pc和pf分別向根方向回退一層*/
}/* end of while */
Ht[i].pstr = (char *) malloc(31-start);
if (!Ht[i].pstr) return ERROR;
strcpy(Ht[i].pstr, (5) );
}/* end of for */
return OK;
}/* end of LeafCode */