閱讀以下說明和C函數(shù),填充函數(shù)中的空缺,將解答填入答題紙的對應欄內。
【說明】
函數(shù)Insert_key(*root ,key)的功能是將鍵值 key 插入到*boot指向根結點的二叉查找樹中(二叉查找樹為空時 *root 為空指針)。若給定的二叉查找樹中已經包含鍵值為 key 的結點,則不進行插入操作井返回 0;否則申請新結點、存入 key 的值并將新結點加入樹中,返回1。
提示:
二叉查找樹又稱為二叉排序樹,它或者是一棵空樹,或者是具有如下性質的二叉樹:
若它的左子樹非空,則其左子樹上所有結點的鍵值均小于根結點的鍵值;
若它的右子樹非空,則其右子樹上所有結點的鍵值均大于根結點的鍵值;
左、右子樹本身就是二叉查找樹。
設二叉查找樹采用二叉鏈表存儲結構,鏈表結點類型定義如下:
Typedef struct BiTnode{
int key_value; /*結點的鍵值,為非負整數(shù)*/
Struct BiTnode*left,*right; /*結點的左、右子樹指針*/
}BiTnode,*BSTree;
【C 函數(shù)】
int Insert_key ( BSTree *root ,int key )
{
BiTnode *father = NULL ,*p = *root ,*s;
while ((1)&& key != p->key_value ) { /*查找鍵值為key的結點*/
father = p;
if ( key < p->key_value) p =(2); /*進入左子樹*/
else p =(3); /*進入右子樹*/
}
if (p) return 0; /*二叉查找樹中己存在鍵值為 key 的結點,無需再插入*/
s = (BiTnode *)malloc ((4)); /*根據(jù)結點類型生成新結點*/
if (!s) return -1;
s->key_value = key; s->left = NULL; s->right = NULL;
if ( !father )
(5); /*新結點作為二叉查找樹的根結點*/
else /*新結點插入二叉查找樹的適當位置*/
if ( key < father->key_value) father->left = s;
else father->right = s;
return 1;
}