2

整数値を格納する二分木で値を検索する次の関数を作成しました (関数はより大きなプログラムの一部です)。

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

問題は、ツリーに存在する値を検索すると、正常に実行されることです。しかし、ツリーに存在しない値を検索すると、プログラムがハングするだけで、プログラムを閉じる必要があります。もう1つ-内部で宣言する代わりに、ノード *temp を引数として渡すことにより、検索関数を再帰的に実装できることを知っています。これにより、プログラムが正しく実行されましたが、何が問題なのか知りたいです上記のコードで。

念のため、ここで完全なプログラムを示します。これにより、障害の発見が容易になります (まだ 2 つの関数しか記述していないことに注意してください)。

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

補足: 私は Dev C++ コンパイラと Windows 7 OS を使用しています。

4

2 に答える 2

6

を入れれば、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;
}
于 2013-01-13T10:59:02.090 に答える
1

std::set

を使用しstd::setます。これは基本的に STL のバイナリ ツリーです。何かを検索したい場合はcount、 、findまたはを使用しますlower_bound。

基本的なデータ構造を実装することは良い練習になりますが、問題のコンパイラ/プラットフォームの特定の知識を持つ専門家によって実装されるため、本番環境では最初に STL を使用するようにしてください。Boostは、もう 1 つの優れたデータ構造と一般的なイディオムのセットです。

于 2013-01-13T16:34:43.137 に答える