c++ - 二分探索木

Question

 template <class T>
void BinaryTree<T>::LoadTree(const char *file)
{
ifstream fin;
fin.open(file);
string buffer;
T buff;
while (!fin.eof())
{
      getline(fin,buffer,'~');
      fin>>buff;

      TreeNode<T> *temp,*temp1;
      temp=Root;
      temp1=temp;
      while (temp!=NULL)
      {
          temp1=temp;  
          TreeNode<T> *Right=temp->RightChild;
          TreeNode<T> *Left=temp->LeftChild;
          if (temp->key>buff)
          {
              temp=temp->LeftChild;
          }
          else if (temp->key<buff)
          {
              temp=temp->RightChild;
          }
      }
      temp=new TreeNode<T>(buff,buffer);          
      if (temp!=Root)
      temp->Parent=temp1;
}
fin.close();
}

私はバイナリ検索ツリーを作成しています。これは、「Alex~ 231423」のような名前とキーを含むファイルの入力を取得する私のコードです。私のコードは正しい BST を作成していますか?は、「このアプリケーションはランタイムに異常な方法で終了するように要求しました。詳細については、アプリケーションのサポートチームに連絡してください」というメッセージです。何が問題なのか本当にわかりません。助けていただければ幸いです ** *前の問題は解決しましたが、次のような insertNode 関数のメッセージが表示されます。

template <class T>
void BinaryTree<T>::insertNode(T Key,string Val)
{

 TreeNode<T> *temp,*temp1;
 temp=Root;
 while (temp!=NULL)
 {
       temp1=temp;
       if (temp->key>Key)
       {
           temp=temp->LeftChild;
       }
       else if (temp->key<Key)
       {
            temp=temp->RightChild;
       }
 }
 temp=new TreeNode<T>(Key,Val);              
 temp->Parent=temp1;
}

これがTreeNode部分です

template <class T>
struct TreeNode{
  string value;
  T key;
  TreeNode<T> *Parent;
  TreeNode<T> *LeftChild;
  TreeNode<T> *RightChild;
  TreeNode (T k,string Val)
  {
           this->value=Val;
           this->key=k;
           this->Parent=NULL;
           this->LeftChild=NULL;
           this->RightChild=NULL;
  }
};

Actually I was getting the error for search function,not insert function.I am sorry for inconvenience.here is the code

template <class T>
string BinaryTree<T>::searchNode(T Key)
{        
TreeNode<T> *temp=Root;
while (temp!=NULL)
{
      if (temp->key==Key)
      {
          return temp->value;
      }
      if (temp->key>Key)
      {
          temp=temp->LeftChild;
      }
      else if (temp->key<Key)
      {
           temp=temp->RightChild;
      }                  
}     
return NULL;
}

score 1 · Accepted Answer

これが問題かどうかはわかりませんが、ポインターへのポインターが必要です。それ以外の場合は、左/右の子メンバーではなく、ローカル変数を変更するだけです。

 TreeNode<T> **temp = &Root,
             *temp1 = NULL; // otherwise Root will have an invalid parent pointer
 while (*temp != NULL)
 {
       temp1 = *temp;
       if (temp1->key > Key)
       {
           temp = &(*temp)->LeftChild;
       }
       else if (temp1->key < Key)
       {
           temp = &(*temp)->RightChild;
       }
 }
 *temp = new TreeNode<T>(Key,Val);              
 (*temp)->Parent = temp1;

score 0 · Accepted Answer

これを書いている方法は、ファイルからしか作成できないことを意味します。operator>>を使用するように記述しますistream。テストも簡単になります。

template <class T>
class BinaryTree {
public:
    istream& operator>>(istream& is) {
        //...
        return is;
    }
};

int main() {
    stringstream ss("tree formatted data");

    BinaryTree<int> tree;
    ss >> tree;
    return 0;
}

"tree formatted data"データが何であれ、置き換えてください。

score 0 · Accepted Answer

さらにいくつかの初期化を行う必要があります (ルートと子):

template <class T>
void BinaryTree<T>::LoadTree(const char *file)
{
   ifstream fin(file);
   string buffer;
   T buff;
  while (getline(fin,buffer,'~') && fin>>buff )
  {
     TreeNode<T> *temp,*temp1;
     temp=Root;
     temp1=temp;
     while (temp!=NULL)
     {
       temp1=temp;  
       TreeNode<T> *Right=temp->RightChild;
       TreeNode<T> *Left =temp->LeftChild;
       if      (temp->key >= buff)      {   temp=temp->LeftChild;      }
       else if (temp->key <  buff)      {   temp=temp->RightChild;     }
     } // allow duplicate key??

     temp=new TreeNode<T>(buff,buffer); 
     if (     !Root)   {  Root=temp;  continue;      }
     //else if (temp !=Root)     temp->Parent=temp1;

     // insert the new node in the correct branch, that was NULL
     if (temp1->key >= buff)
      {
          temp1->LeftChild=temp;
      }
     else temp1->RightChild=temp;
  }
fin.close();
}

また、失敗した場合、searchNode は "" を返す必要がありますか?? ただし、NULL ではありません。

c++ - 二分探索木

3 に答える 3

Related

Reference