閱讀以下說明、C 函數(shù)和問題,將解答填入答題紙的對(duì)應(yīng)欄內(nèi)。
【說明】
二叉查找樹又稱為二叉排序樹,它或者是一棵空樹,或者是具有如下性質(zhì)的二叉樹:
若它的左子樹非空,則其左子樹上所有結(jié)點(diǎn)的鍵值均小于根結(jié)點(diǎn)的鍵值;
若它的右子樹非空,則其右子樹上所有結(jié)點(diǎn)的鍵值均大于根結(jié)點(diǎn)的鍵值;
左、右子樹本身就是二叉查找樹。
設(shè)二叉查找樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu),鏈表結(jié)點(diǎn)類型定義如下:
typedef struct BiTnode{
int key_value; /*結(jié)點(diǎn)的鍵值,為非負(fù)整數(shù)*/
struct BiTnode *left,*right; /*結(jié)點(diǎn)的左、右子樹指針*/
}*BSTree;
函數(shù)find_key(root, key)的功能是用遞歸方式在給定的二叉查找樹(root指向根結(jié)點(diǎn))中查找鍵值為key的結(jié)點(diǎn)并返回結(jié)點(diǎn)的指針;若找不到,則返回空指針。
【函數(shù)】
BSTree find_key(BSTree root, int key)
{
if ( (1) )
return NULL;
else
if (key == root-> key_value)
return (2) ;
else if (key < root -> key_value)
return (3) ;
else
return (4) ;
}
【問題1】
請(qǐng)將函數(shù)find_key中應(yīng)填入(1)~(4)處的字句寫在答題紙的對(duì)應(yīng)欄內(nèi)。
【問題2】
若某二叉查找樹中有n個(gè)結(jié)點(diǎn),則查找一個(gè)給定關(guān)鍵字時(shí),需要比較的結(jié)點(diǎn)個(gè)數(shù)取決于 (5) 。