He escrito la siguiente función para buscar un valor en un árbol binario almacenar valores enteros (la función es parte de un programa más amplio):

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;   
}    

El problema es: cuando la búsqueda de un valor presente en el árbol, funciona muy bien. Pero si la búsqueda de un valor que no están presentes en el árbol, el programa se cuelga, y tengo que cerrarlo.
Una cosa más – sé que podemos implementar la función de búsqueda de forma recursiva por pasar nodo *temp como un argumento, en lugar de declarar en su interior, y lo he hecho que hizo que el programa se ejecute correctamente, pero quiero saber cuál es el problema en el código anterior.

Estoy dando el programa completo aquí, sólo en caso de que esto hace que la detección de errores más fácil( por favor, tenga en cuenta que he escrito sólo dos funciones de todavía):

#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;
}               

Lado nota : estoy usando Dev C++ compilador y sistema operativo Windows 7.

  • Puede dar formato a tu código fuente? Es difícil de leer.
  • Hay una razón por la que no estás usando std::set?
  • Sí, la razón es que no sé qué std::set es. Soy un principiante en la programación.
  • La persona en respuesta va a funcionar, pero de una manera aún mejor es temp = (num > temp->data) ? temp->right : temp->left que permite que el compilador utiliza el cmov instrucciones.
InformationsquelleAutor Parth | 2013-01-13

2 Comentarios

  1. 6

    Poner else y el problema desaparecerá.

    Porque después de temp = temp->right; debe comprobar temp de nuevo, pero en su código original inmediatamente de la prueba temp->data que no puede ser un puntero válido.

    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;
    }
    • Gracias Raymond. Trabajó como por arte de magia. Es increíble lo rápido que ha obtenido una respuesta. Muchas gracias.
    • Tiene que trabajó realmente?
    • Sí, que ha trabajado realmente. Sólo por curiosidad, ¿por qué la duda?
    • Dudo porque básicamente tiene 3 casos (==, >, <), y sólo uno puede ser cierto, así que no sé por qué los demás ayudaron, otros que para mejorar la legibilidad (la que usted necesita para trabajar en general – Google «Estilo Artístico C++ formato»)
    • la cosa funcionó, porque en caso de que la segunda condición si funciona, va a incrementar la temperatura a la temperatura->a la derecha… ahora la tercera si la condición se comprueba con el nuevo valor de temp. Aquí, la temp probablemente se incrementará a temp->a la derecha sin comprobar el valor NULL. Supongo que es la razón por la que usted está recibiendo un problema cuando el número no está en el árbol.
  2. 1

    std::set

    Utilizar un std::set; básicamente se trata de STL del árbol binario. Si quieres buscar algo, tendría que usar cuenta, buscar o lower_bound.

    La aplicación básica de las estructuras de datos son buenos ejercicios, pero en la producción, pruebe a utilizar la STL en primer lugar, como son implementadas por los profesionales con los conocimientos específicos del compilador/plataforma en cuestión. Boost es otro gran conjunto de estructuras de datos comunes y frases hechas.

Dejar respuesta

Please enter your comment!
Please enter your name here