希賽網(wǎng)2024下半年軟件設(shè)計(jì)師第一期模考活動已結(jié)束，現(xiàn)將2024下半年軟件設(shè)計(jì)師第一期?？荚嚲恚ò咐治觯┓窒斫o大家。本資料的PDF版本可在本文文首本文資料處或文末的資料下載欄目下載。

2024下半年軟件設(shè)計(jì)師第一期?？荚嚲恚ò咐治觯┎糠衷囶}如下：

1、閱讀下列函數(shù)說明和C函數(shù)，將應(yīng)填入    （n）    處的字句寫在答題紙的對應(yīng)欄內(nèi)。

[函數(shù)5說明]

　　函數(shù)DeleteNode（Bitree *r，int e）的功能是：在樹根結(jié)點(diǎn)指針為r的二叉查找（排序）樹上刪除鍵值為e的結(jié)點(diǎn)，若刪除成功，則函數(shù)返回0，否則函數(shù)返回-1。二叉查找樹結(jié)點(diǎn)的類型定義為：

typedef struct Tnode{

int data；

struct Tnode *Lchild，*Rchild；

}*Bitree；

　　在二叉查找樹上刪除一個結(jié)點(diǎn)時(shí)，要考慮三種情況：

　　1若待刪除的結(jié)點(diǎn)p是葉子結(jié)點(diǎn)，則直接刪除該結(jié)點(diǎn)；

　　2若待刪除的結(jié)點(diǎn)p只有一個子結(jié)點(diǎn)，則將這個子結(jié)點(diǎn)與待刪除結(jié)點(diǎn)的父結(jié)點(diǎn)直接連接，然后刪除結(jié)點(diǎn)p；

　　3若待刪除的結(jié)點(diǎn)p有兩個子結(jié)點(diǎn)，則在其左子樹上，用中序遍歷尋找關(guān)鍵值最大的結(jié)點(diǎn)s，用結(jié)點(diǎn)s的值代替結(jié)點(diǎn)p的值，然后刪除結(jié)點(diǎn)s，結(jié)點(diǎn)s必屬于上述1、2情況之一。

問題內(nèi)容：

[函數(shù)5]

int DeleteNode（Bitree *r，int e） {

　　Bitree p = *r， pp， s， c；

　　while （  （1）     ） { /*從樹根結(jié)點(diǎn)出發(fā)查找鍵值為e的結(jié)點(diǎn)*/

　　　pp = p；

　　　if （ e< p->data） p = p -> Lchild；

　　　else p = p->Rchild；

　　}

　　if （!p） return -1；  /* 查找失敗 */

　　if （p->Lchild && p->Rchild） { /* 處理情況3 */

　　　s = （2）；pp = p；

　　　while （  （3） ） { pp = s； s = s-> Rchild； }

　　　p->data = s ->data； p = s；

　　}

　　/* 處理情況1、2*/

　　if （ （4） ） c = p -> Lchild；

　　else c = p -> Rchild；

　　if （p == *r） *r = c；

　　if （ （5）     ） pp -> Lchild = c；

　　else pp->Rchild = c；

　free（p）；

　return 0；

　}

試題答案：

（1）p&&p->data !＝e 或 p&&（*p）.data !＝e

（2）p->Lchild 或 （*p）.Lchild

（3）s->Rchild 或 （*s）.Rchild

（4）p->Lchild 或 （*p）.Lchild

（5）p==pp->Lchild 或 p （*pp）.Lchild