C++ 在二叉树中搜索
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/14302754/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
search in a binary tree
提问by Parth
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.
问题是：当我搜索树中存在的值时，它运行良好。但是如果我搜索树中不存在的值，程序就会挂起，我必须关闭它。还有一件事 - 我知道我们可以通过将 node *temp 作为参数传递来递归地实现搜索功能，而不是在内部声明它，我已经这样做了，这导致程序正确运行，但我想知道是什么问题在上面的代码中。
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.
旁注：我正在使用 Dev C++ 编译器和 Windows 7 操作系统。
回答by Raymond.Carl
Put an elseand your problem will disappear.
放一个else，你的问题就会消失。
Because after temp = temp->right;you must check tempagain but in your original code you immediately test temp->datawhich may not be a valid pointer.
因为在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;
}
回答by Alex Chamberlain
std::set
std::set
Use a std::set; it is basically STL's binary tree. If you want to search for something, you would use count, findor lower_bound.
使用std::set; 它基本上是STL的二叉树。如果要搜索某些内容，可以使用count,find或lower_bound。
Implementing basic data structures are good exercises, but in production, try to use STL first, as they are implemented by professionals with specific knowledge of the compiler/platform in question. Boostis another great set of data structures and common idioms.
实现基本数据结构是很好的练习，但在生产中，首先尝试使用 STL，因为它们是由对相关编译器/平台具有特定知识的专业人员实现的。Boost是另一组很棒的数据结构和常用习惯用法。
