m0_63999697 2022-05-19 16:04 采纳率: 93.5%
浏览 43
已结题

怎么查找二叉搜索树上的值(广义表)

问题描述
给定一个二叉搜索树(广义表形式)以及某个整数x,检查x是否在二叉搜索树上。

输入
输入第一行是二叉搜索树的的广义表表示。该行最长不超过2000000个字符。
第二行是一个正整数n,表示有n个测试。
接下来每行一个整数x。

输出
输出总共n行,如果x在二叉搜索树上,输出yes,否则输出no。

输入样列
6(3(1(,2),5(4,)),127)
3
5
8
127
输出样例
yes
no
yes

#include<bits/stdc++.h>
using namespace std;
typedef int ElementType;
typedef  struct  Node{
    ElementType  data;
    struct Node  *lchild;
    struct Node  *rchild;
}BSTNode, *BSTree;
BSTree createTree(char s[])
{
    BSTree f[1010],p;
    BSTree B=NULL;
    int top=0,k=0;
    for(int i=0;s[i]!='\0';i++){
        if(isalpha(s[i])){
            p=new BSTNode;
            p->data=s[i];
            p->lchild=NULL;
            p->rchild=NULL;
            if(B==NULL){
                B=p;
            }
            if(k==1){
                f[top]->lchild=p;
            }
            if(k==2){
                f[top]->rchild=p;
            }
        }
        else if(s[i]=='('){
            top++;
            f[top]=p;
            k=1;
        }
        else if(s[i]==','){
            k=2;
        }
        else if(s[i]==')'){
            top--;
        }
    }
    return B;
}
BSTNode* findMin(BSTree bst)
{
    BSTree p=bst;
    if(bst==NULL){
        return NULL;
    }
    while(p->lchild!=NULL){
        p=p->lchild;
    }
    return p;
}
BSTNode* findMax(BSTree bst)
{
    BSTree p=bst;
    if(bst==NULL){
        return NULL;
    }
    while(p->rchild!=NULL){
        p=p->rchild;
    }
    return p;
} 
BSTNode* find(BSTree bst, ElementType x)
{
    if(bst==NULL) return NULL;
    else if(x<bst->data) return find(bst->lchild,x);
    else if(x>bst->data) return find(bst->rchild,x);
    else return bst;
}
void printTree(BSTree bt)
{
    if(bt!=NULL){
        printf("%c",bt->data);
        if(bt->lchild!=NULL||bt->rchild!=NULL){
            printf("(");
            printTree(bt->lchild);
            printf(",");
            printTree(bt->rchild);
            printf(")");
        }
    }
}
int main()
{
    int n,a,i;
    char str[2000000];
    BSTNode *t,*k;
    gets(str);
    t=createTree(str[2000000]);
    for(i=0;i<n;i++){
        cin >> a;
        k=find(t,a);
        if(k!=NULL) puts("yes");
        else puts("no");
    }
    return 0;
}


  • 写回答

1条回答 默认 最新

  • 张十五 2022-05-19 16:35
    关注

    分割字符串(分割广义表),,,存储分割出来的字符串,,,,按字符串形式接受要检查的节点值,,,,,,,,遍历存储,strcmp(),,,有一个==0 YES,否则NO

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 5月28日
  • 已采纳回答 5月20日
  • 创建了问题 5月19日

悬赏问题

  • ¥15 前后端分离的学习疑问?
  • ¥15 stata实证代码答疑
  • ¥15 MATLAB数据处理插值
  • ¥50 husky+jaco2实现在gazebo与rviz中联合仿真
  • ¥15 dpabi预处理报错:Error using y_ExtractROISignal (line 251)
  • ¥15 在虚拟机中配置flume,无法将slave1节点的文件采集到master节点中
  • ¥15 husky+kinova jaco2 仿真
  • ¥15 zigbee终端设备入网失败
  • ¥15 金融监管系统怎么对7+4机构进行监管的
  • ¥15 硬件IIC从模式的数据发送,中断数据的接收,不能用HAL库(按照时序图)