建立一個(gè)二叉排序樹(shù)，根據(jù)給定值對(duì)其實(shí)施查找。

在屏南等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作 網(wǎng)站設(shè)計(jì)制作按需網(wǎng)站開(kāi)發(fā),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),品牌網(wǎng)站制作,成都全網(wǎng)營(yíng)銷,外貿(mào)網(wǎng)站制作,屏南網(wǎng)站建設(shè)費(fèi)用合理。

二叉排序樹(shù)的二叉鏈表存儲(chǔ)表示：

typedef int ElemType;
typedef  struct  BSTNode
{  
    ElemType  data;
    struct  BSTNode   *lchild,*rchild;
}BSTNode,*BSTree;

函數(shù)接口定義：

下面給出了?二叉排序樹(shù)創(chuàng)建和搜索?函數(shù)的大部分內(nèi)容，但缺少了一部分（以下劃線____標(biāo)識(shí)出來(lái)的部分）。

請(qǐng)先將以下代碼中畫橫線的部分補(bǔ)充完整，然后將完整的函數(shù)BSTInsert,BSTCreate,BSTSearch提交系統(tǒng)，完成題目要求的功能。

void BSTInsert( BSTree &T, BSTree s)
{
    if(T==NULL)
        T=s;
    else if(s->datadata)
        BSTInsert( ____ ,s);
    else 
        BSTInsert( ____ ,s);
}

void BSTCreate(BSTree  &T)
{   
    ElemType x;  BSTree  s;
    T=NULL;
    cin>>x;
    while (x!=-1)
    {  
        s=new BSTNode;
        s->data=x;
        s->lchild=s->rchild=NULL;
        BSTInsert( ____ ,  ____ );
        cin>>x;
    }
}

BSTree BSTSearch(BSTree T, ElemType k)
{  
    if(!T || ____ )
        return ____ ;
    if(kdata)
        return  BSTSearch( ____ ,k);
    else
        return  BSTSearch ( ____ ,k);
}

該函數(shù)中的參數(shù)說(shuō)明：

ElemType k要搜索的值

順序表中第一個(gè)數(shù)據(jù)元素存儲(chǔ)在?T.R[1]

測(cè)試主程序樣例：

int main ()
{    BSTree T,p; int x;
    BSTCreate(T);
    cin>>x;
    p=BSTSearch(T,x);
    if(p!=NULL)
    {  cout<<"have found!";
       cout<<" lchild:";
       if(p->lchild) cout<lchild->data;
       else cout<<"NULL";
       cout<<" rchild:";
       if(p->rchild) cout<rchild->data;
       else cout<<"NULL";
    }
    else
       cout<<"NOT FOUND!";
    return 0;
}

輸入格式:

第一行輸入二叉排序樹(shù)中結(jié)點(diǎn)的值，以-1結(jié)束。用逐個(gè)插入的方式創(chuàng)建二叉排序樹(shù)。

第二行輸入一個(gè)要查找的值。

輸出格式:

找到，輸出have found!。接著空一格，輸出該結(jié)點(diǎn)左孩子值，后再空一格，輸出該結(jié)點(diǎn)右孩子的值。如果孩子為空，對(duì)應(yīng)位置輸出NULL。

如果沒(méi)有找到，輸出NOT FOUND!。

輸入樣例:

10 18 3 8 20 2 7 -1
3

輸出樣例:

have found! lchild:2 rchild:8

輸入樣例2:

10 18 3 8 20 2 7 -1
8

輸出樣例2:

have found! lchild:7 rchild:NULL

輸入樣例3:

10 18 3 8 20 2 7 -1
5

輸出樣例3:

NOT FOUND!

AC

void BSTInsert(BSTree& T, BSTree s)
{
    if (T == NULL)
        T = s;
    else if (s->data< T->data)
        BSTInsert((T->lchild), s);
    else
        BSTInsert((T->rchild), s);
}

void BSTCreate(BSTree& T)
{
    ElemType x;  BSTree  s;
    T = NULL;
    cin >>x;
    while (x != -1)
    {
        s = new BSTNode;
        s->data = x;
        s->lchild = s->rchild = NULL;
        BSTInsert(T, s);
        cin >>x;
    }
}

BSTree BSTSearch(BSTree T, ElemType k)
{
    if (!T || T->data == k)
        return T;
    if (k< T->data)
        return  BSTSearch(T->lchild, k);
    else
        return  BSTSearch(T->rchild, k);
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁(yè)名稱：6-7數(shù)據(jù)結(jié)構(gòu)考題-二叉排序樹(shù)-創(chuàng)新互聯(lián)
本文來(lái)源：http://weahome.cn/article/jddio.html