将不在树中的参数传递给搜索函数时，二叉搜索树算法崩溃

Question

我尝试构建一个二叉搜索树，当我给它参数时一切正常，但我想看看当它在树中找不到 int 时它是否会打印 0当我调用搜索时它崩溃了。

我尝试在第一个 if 语句之后添加一个条件，但这破坏了递归这是代码：

   struct node
{
  int data;
  node* left;
  node* right;
  
  node(int d)
  {
    data = d; 
    left = right = NULL;

  }

};

node* insert(node *root, int n)
{
  if(root == NULL)
  {
    return new node(n);
  }
  else
  {
    node* y;

    if(n <= root->data)
    {
      y = insert(root->left, n);
      root->left = y;
    }
    else
    {
      y = insert(root->right, n);
      root->right = y;
    }

    return root;
  }

}

node* search(node *root,int n)
{
  if(root == NULL || root->data == n)
  {
    return root;
  }
  
  if(root->data < n)
  {
    return search(root->right, n);
  }
  return search(root->left, n);
}

int treemax(node *root)
{
   while(root->right != NULL)
   {
     root = root->right;
   }
   return root->data;
}

int treemin(node *root)
{
  while(root->left != NULL)
  {
    root = root->left;
  }
  return root->data;
}

int main()
{
   node *R = NULL;
   R = insert(R, 33);
   insert(R,12);
   insert(R, 40);
   insert(R, 36);
   insert(R, 21);
  
  
  cout << search(R, 65)->data << endl;
  
  
}

Answer 1

当你运行

cout << search(R, 65)->data << endl;

search(R, 65)returnsNULL。您不能通过对其执行 ->data 来取消引用 NULL。你可能想要：

Node* result = search(R, 65);
if (result)
{
    cout << result->data << endl;
}
else
{
    cout << "Not found" << endl;
}

Answer 2

您的问题是您正在尝试访问空指针。来自 search(R,65) 的指针 return 为空，因为在最后一步你的 root->right 是 null。如果你想 return 0 如果没有找到元素你可以用这个替换你的最后一行：

node *result = search(R, 65);
if (result)
 cout << result->data << endl;
else 
 cout << "0" << endl;

Answer 3

下面是一个工作示例。我添加了一些注释，说明您可以在上述程序中更改哪些内容以使其安全或更好。

#include<iostream>
struct node
{
//always initialize built-in type data members  
int data = 0;//initialize any built in type otherwise it will have garbage value
  node* left = nullptr;//initialize any built type as stated above
  node* right = nullptr;//initialize any built in type as stated above
  
  node(int d)
  {
    data = d; 
    left = right = nullptr;

  }

};

node* insert(node *root, int n)
{
  if(root == nullptr)
  {
    return new node(n);
  }
  else
  {
    node* y;

    if(n <= root->data)
    {
      y = insert(root->left, n);
      root->left = y;
    }
    else
    {
      y = insert(root->right, n);
      root->right = y;
    }

    return root;
  }

}

node* search(node *root,int n)
{
  if(root == nullptr || root->data == n)
  {
    return root;
  }
  
  if(root->data < n)
  {
    return search(root->right, n);
  }
  return search(root->left, n);
}

int treemax(node *root)
{
   while(root->right != nullptr)
   {
     root = root->right;
   }
   return root->data;
}

int treemin(node *root)
{
  while(root->left != nullptr)
  {
    root = root->left;
  }
  return root->data;
}

int main()
{
   node *R = nullptr;
   R = insert(R, 33);
   insert(R,12);
   insert(R, 40);
   insert(R, 36);
   insert(R, 21);
  
  
  //std::cout << search(R, 65)->data << std::endl;
    node *value = search(R, 65);
    
    //check if the pointer is valid
    if(value)
    {
        std::cout<< value->data <<std::endl;
    }
    else 
    {
        std::cout<<"cannot access nullptr"<<std::endl;
    }
    
  
  
}

错误是因为 search(R, 65); 正在返回 NULL 而您试图访问 NULL 指针的数据成员值。

将不在树中的参数传递给搜索函数时，二叉搜索树算法崩溃

Binary search tree algorithm crashing when passing a parameter that isn't in the tree to the search function

c++

algorithm

binary-search-tree