搜索二叉树 [英] search in a binary tree

问题描述

我写了以下函数来搜索存储整数值的二叉树中的值（该函数是较大程序的一部分）：

  bool tree :: search（int num）//函数属于类'tree'
 {
 node * temp = head; //'head'是指向根节点的指针
 
 while（temp！= NULL）
 {
 if（temp-> data == num）
 break ; 
 
 if（num> temp-> data）
 temp = temp-> right; 
 
 if（num< temp-> data）
 temp = temp-> left; 
} 
 
 if（temp == NULL）
 return false; 
 else if（temp-> data == num）
 return true; 
} 
  

问题是：当我在树中搜索一个值时，运行良好。但是如果我搜索一个值不存在于树中，程序只是挂起，我必须关闭它。
另外一件事 - 我知道我们可以通过传递node * temp作为参数来递归地实现搜索函数，而不是在里面声明它，我这样做导致程序正确运行，但我想知道在上面的代码中有什么问题。

我在这里提供完整的程序，只是为了使故障查找更容易（请注意，我只写了两函数）：

 ＃include< iostream> 
 using namespace std; 
 
 struct node 
 {
 int data; 
 node * left; 
 node * right; 
}; 
 
类树
 {
 public：
 node * head; //指向根的指针
 int count; //存储树中的元素数量
 tree（）; 
 void addnode（int）; 
 void deletenode（int）; 
 bool search（int）; 
 int minimum（）; 
 int maximum（）; 
 void inorder（）; 
 void preorder（）; 
 void postorder（）; 
 void printtree（）; 
 int mthlargest（）; // found'm'th maximum element 
 int mthsmallest（）; //找到第m个最小元素
 void convert（）; // convert binary tree to linked list 
}; 
 
 tree :: tree（）
 {
 head = NULL; 
 count = 0; 
} 
 
 void tree :: addnode（int num）
 {
 node * temp = new node; 
 temp-> data = num; 
 temp-> left = NULL; 
 temp-> right = NULL; 
 
 node ** ptr =& head; // double pointer 
 
 while（* ptr！= NULL）
 {
 if（num>（* ptr） - > data）
 ptr =& （（* ptr） - > right）; 
 
 if（num <（* ptr） - > data）
 ptr =&（（* ptr） - > left）; 
} 
 
 * ptr = temp; 
} 
 
 
 bool tree :: search（int num）
 {
 node * temp = head; 
 
 while（temp！= NULL）
 {
 if（temp-> data == num）
 break; 
 
 if（num> temp-> data）
 temp = temp-> right; 
 
 if（num< temp-> data）
 temp = temp-> left; 
} 
 
 if（temp == NULL）
 return false; 
 else if（temp-> data == num）
 return true; 
} 
 
 
 
 
 int main（）
 {
 tree ob; 
 ob.addnode（2）; 
 
 ob.search（2）; 
 
 ob.search（3）; 
 
 ob.search（-1）; 
 ob.search（2）; 
 cout<< endl<< endl; 
 
系统（pause）; 
 return 0; 
} 
  

注意：我使用Dev C ++编译器和Windows 7操作系统。 p>

解决方案

放置 else ，您的问题就会消失。

$因为在 temp = temp-> right; 之后，必须检查 temp 但是在原始代码中，您将立即测试 temp-> data ，这可能不是有效的指针。

  bool tree :: search（int num）
 {
 node * temp = head; 
 
 while（temp！= NULL）
 {
 if（temp-> data == num）
 break; 
 
 if（num> temp-> data）
 temp = temp-> right; 
 else //< --- Put this'else'here 
 if（num< temp-> data）
 temp = temp-> left; 
} 
 
 if（temp == NULL）
 return false; 
 
 if（temp-> data == num）
 return true; 
 
 return false; 
} 
  

I have written the following function to search for a value in a binary tree storing integer values (the function is part of a larger program):

bool tree::search(int num)       //the function belongs to class 'tree'
{
   node *temp=head;      //'head' is pointer to root node

   while(temp!=NULL)
   {
      if(temp->data==num)
         break;

      if(num>temp->data)
         temp=temp->right;

      if(num<temp->data)
         temp=temp->left;
   }

   if(temp==NULL)
      return false;
   else if(temp->data==num)
         return true;   
}    

The problem is: when I search for a value present in the tree, it runs fine. But if I search for a value not present in the tree, the program just hangs, and I have to close it. One more thing - I know we can implement the search function recursively by passing node *temp as an argument, instead of declaring it inside, and I have done so which caused the program to run correctly, but I want to know what is the problem in the above code.

I am giving the full program here, just in case it makes fault- finding easier( please note that I have written only two functions yet):

#include<iostream>
using namespace std;

struct node
{
int data;
node *left;
node *right;
};

class tree
{
public:
    node *head;    //pointer to root
    int count;     //stores number of elements in tree
    tree();
    void addnode(int);
    void deletenode(int);
    bool search(int);
    int minimum();
    int maximum();
    void inorder();
    void preorder();
    void postorder();
    void printtree();
    int mthlargest();     //finds 'm'th largest element
    int mthsmallest();    //finds 'm'th smallest element
    void convert();       //converts binary tree to linked list
};

tree::tree()
{
   head=NULL;
   count =0;
}

void tree::addnode(int num)
{
   node *temp= new node;
   temp->data=num;
   temp->left=NULL;
   temp->right=NULL;

   node **ptr=&head;          //double pointer

   while(*ptr!=NULL)
   {
      if(num>(*ptr)->data)
         ptr=&((*ptr)->right);

      if(num<(*ptr)->data)
         ptr=&((*ptr)->left);
   }

   *ptr=temp;
}


bool tree::search(int num)
{
   node *temp=head;

   while(temp!=NULL)
   {
      if(temp->data==num)
         break;

      if(num>temp->data)
         temp=temp->right;

      if(num<temp->data)
         temp=temp->left;
   }

   if(temp==NULL)
      return false;
   else if(temp->data==num)
      return true;   
}    




int main()
{
   tree ob;
   ob.addnode(2);

   ob.search(2);

   ob.search(3);

   ob.search(-1);
   ob.search(2);
   cout<<endl<<endl;

   system("pause");
   return 0;
}               

Side note : I am using Dev C++ compiler and Windows 7 OS.

解决方案

Put an else and your problem will disappear.

Because after temp = temp->right; you must check temp again but in your original code you immediately test temp->data which may not be a valid pointer.

bool tree::search(int num)
{
    node *temp = head;

    while (temp != NULL)
    {
        if (temp->data == num)
            break;

        if (num > temp->data)
            temp = temp->right;
        else                  //  <--- Put this 'else' here
        if (num < temp->data)
            temp = temp->left;
    }

    if (temp == NULL)
        return false;

    if (temp->data == num)
        return true;

    return false;
}

这篇关于搜索二叉树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！