在c ++中纠正二进制搜索树搜索函数的代码（更新的问题） [英] rectify the code of binary search tree search function in c++(updated question)

问题描述

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<process.h>

struct tree_node
{
	tree_node *left;
	tree_node *right;
	int data;
	char r;
} ;
class bst
{
	tree_node *root;
	public:
	bst()
	{
		root=NULL;
	}
	int isempty()
	{
		return(root==NULL);
	}
	void insert(int item);
	void inordertrav();
	void inorder(tree_node *);
	void postordertrav();
	void postorder(tree_node *);
	void preordertrav();
	void preorder(tree_node *);
	int search(tree_node * ,int);
};
void bst::insert(int item)
{
	tree_node *p=new tree_node;
	tree_node *previous;
	p->data=item;
	p->left=NULL;
	p->right=NULL;
	previous=NULL;
	if(isempty())
		root=p;
	else
	{
		tree_node *current;
		current=root;
		while(current!=NULL)
		{
			previous=current;
			if(item<current->data)
				current=current->left;
			else
				current=current->right;
		}
		if(item<previous->data)
			previous->left=p;
		else
			previous->right=p;
	}
}
void bst::inordertrav()
{
	inorder(root);
}
void bst::inorder(tree_node *current)
{
	if(current!=NULL)
	{
		inorder(current->left);
		cout<<"  "<<current->data<<"     ";
		inorder(current->right);
	}
}
void bst::postordertrav()
{
	postorder(root);
}
void bst::postorder(tree_node *current)
{
	if(current!=NULL)
	{
		postorder(current->left);
		postorder(current->right);
		cout<<"  "<<current->data<<"     ";
	}
}
void bst::preordertrav()
{
	preorder(root);
}
void bst::preorder(tree_node *current)
{
	if(current!=NULL)
	{
		cout<<"  "<<current->data<<"     ";
		preorder(current->left);
		preorder(current->right);
	}
}

int bst::search(tree_node* root,int data) {
	int r;
	if(root == NULL) {
	   //	r='f';
		return 0;
	}
	else if (root != NULL){
	if(root->data == data) {
	   //	r='t';
		return 1;
	}
	}
	else if(data <= root->data) {
	      return search(root->left,data);
	}
	else {
	      return search(root->right,data);
	}

}
void main()
{
	int digit;
	bst b;
	tree_node *root;
	/*b.insert(52);
	b.insert(25);
	b.insert(50);
	b.insert(15);
	b.insert(40);
	b.insert(45);
	b.insert(20); */
	cout<<"insert the nodes in the BT";
	cout<<"enter integer: to quit enter 0";
	cin>>digit;
	while (digit!=0)
	{
		b.insert(digit);
		cin>>digit;
	}
		 cout<<"inorder"<<endl;
	b.inordertrav();
	cout<<endl<<"postorder"<<endl;
	b.postordertrav();
	cout<<endl<<"preorder"<<endl;
	b.preordertrav();
	int number;
	cout<<"Enter number be searched\n";
	cin>>number;
	//If number is found, print "FOUND"
	int c;
	c=b.search(root,number);
	cout<<"returned value"<<c;
	if (c==1) cout<<"Found\n";
	else cout<<"Not Found\n";
	getch();
}

搜索功能总是返回相同的值，无论它是否在BST中。

请帮我弄清楚错误。

上面的代码没有编译错误。

The search function is always returning the same value whether it is in the BST or not.
Please help me to figure out the error.
The above code has no compile error.

推荐答案

上面的代码< b>确实有编译错误，但你必须禁止它。在函数结束时，下面描述的代码路径没有 return 语句。



在你的搜索函数，如果 root 包含的数据值等于你的输入参数，那么它将返回 1 。但是，如果该值不等于您的输入参数，它将通过其余代码落下并返回一些随机（但可能相同）的值。使用调试器逐步执行代码很容易发现。

The above code does have a compile error, but you must have it suppressed. At the end of the function there is no return statement for the code path described below.

In your search function, if root contains a data value that is equal to your input parameter, then it will return 1. However, if the value is not equal to your input parameter, it will fall through the rest of the code and return some random (but possibly the same) value. Easy to spot by stepping through the code with the debugger.

更改

Change

int bst::search(tree_node* root,int data) {
    int r;
    if(root == NULL) {
       //   r='f';
        return 0;
    }
    else if (root != NULL){
    if(root->data == data) {
       //   r='t';
        return 1;
    }
    }
    else if(data <= root->data) {
          return search(root->left,data);
    }
    else {
          return search(root->right,data);
    }

}

to

to

int bst::search(tree_node* root,int data) {
    int r;
    if(root == NULL) {
       //   r='f';
        return 0;
    }
    else if (root != NULL){
    if(root->data == data) {
       //   r='t';
        return 1;
    }
    else if(data <= root->data) {
          return search(root->left,data);
    }
    else {
          return search(root->right,data);
    }
    }

}

当然，如果你缩进了这个问题会更容易发现代码正确：

Of course, the issue would have been easier to spot if you had indented the code correctly:

int bst::search(tree_node* root,int data) {
    int r;
    if(root == NULL) {   // test root value
       //   r='f';
        return 0;
    }
    else if (root != NULL){ // test root value (hmmm... see comment below)
        if(root->data == data) {
           //   r='t';
            return 1;
        }
    }
    else if(data <= root->data) { // testing again, in case root is neither "NULL" nor "not NULL" (wait, what?)
          return search(root->left,data);
    }
    else {
          return search(root->right,data);
    }

}

如果你删除了冗余，这将更加明显第二次测试：

It would have been even more obvious if you had removed the redundand second test:

int bst::search(tree_node* root,int data) {
    int r;
    if(root == NULL) {       // checking for NULL here
       //   r='f';
        return 0;
    }
    else /*if (root != NULL)*/{ // if I'm here, then root can not be NULL!
        if(root->data == data) {
           //   r='t';
            return 1;
        }
    }
    else if(data <= root->data) { // <-- this will issue a compile error now!
          return search(root->left,data);
    }
    else {
          return search(root->right,data);
    }

}

经验教训：

1。正确格式化代码以提高可读性和在编译代码之前发现错误的能力

2.检查条件语句是否有冗余检查并让编译器帮助您找到逻辑错误

3.修复上一版本中的语法错误后，编译器可能会注意到返回丢失（参见解决方案1）;可能它之前没有打扰过错误消息，因为它意识到它无论如何都不会到达函数的末尾。

Lessons learned:
1. format the code correctly to improve readability and the ability to spot errors before even compiling the code
2. check your conditional statements for redundant checks and have the compiler help you find logical errors
3. Once you fix the syntax error in the last version, the compiler will likely notice that there is a return missing (see solutuion 1); probably it didn't bother with an error message before because it realized it would never get to the end of the function anyway.

这篇关于在c ++中纠正二进制搜索树搜索函数的代码（更新的问题）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！