6-7数据结构考题-二叉排序树-创新互联
建立一个二叉排序树,根据给定值对其实施查找。
在屏南等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供网站设计、成都网站制作 网站设计制作按需网站开发,公司网站建设,企业网站建设,品牌网站制作,成都全网营销,外贸网站制作,屏南网站建设费用合理。二叉排序树的二叉链表存储表示:
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!
ACvoid 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://myzitong.com/article/jddio.html