建立一个二叉排序树，根据给定值对其实施查找。

在屏南等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供网站设计、成都网站制作 网站设计制作按需网站开发,公司网站建设,企业网站建设,品牌网站制作,成都全网营销,外贸网站制作,屏南网站建设费用合理。

二叉排序树的二叉链表存储表示：

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

函数接口定义：

下面给出了 二叉排序树创建和搜索 函数的大部分内容，但缺少了一部分（以下划线____标识出来的部分）。

请先将以下代码中画横线的部分补充完整，然后将完整的函数BSTInsert,BSTCreate,BSTSearch提交系统，完成题目要求的功能。

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);
}

该函数中的参数说明：

ElemType k要搜索的值

顺序表中第一个数据元素存储在 T.R[1]

测试主程序样例：

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;
}

输入格式:

第一行输入二叉排序树中结点的值，以-1结束。用逐个插入的方式创建二叉排序树。

第二行输入一个要查找的值。

输出格式:

找到，输出have found!。接着空一格，输出该结点左孩子值，后再空一格，输出该结点右孩子的值。如果孩子为空，对应位置输出NULL。

如果没有找到，输出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);
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

当前文章：6-7数据结构考题-二叉排序树-创新互联
当前地址：http://kswsj.cn/article/jddio.html