バイナリ検索ツリーで複数のノードを削除する

Question

バイナリ検索ツリーでどのようにノードを削除するのかよく分かりません。私は、これは

bool remove(value_type& data) 
{ 
    return remove(root, data); 
} 

私は学生のオブジェクトとそれを呼び出す

bool remove(BTNode<value_type>* cNode, value_type& data) 
{ 
    if(cNode == NULL) 
    { 
     return false; 
    } 

    if(data.get_name() > cNode->get_data().get_name()) 
    { 
     remove(cNode->get_right(), data); 
    } 
    else if(data.get_name() < cNode->get_data().get_name()) 
    { 
     remove(cNode->get_left(), data); 
    } 
    else 
    { 
     if(cNode->is_leaf()) 
     { 
      if(root->get_data().get_name() == data.get_name()) 
      { 
       root = NULL; 
      } 
      else 
      { 
       if(cNode->is_right_child()) 
       { 
        cNode->get_parent()->set_right(NULL); 
       } 
       else 
       { 
        cNode->get_parent()->set_right(NULL); 
       } 
      } 
      delete cNode ; 
      size--; 
     } 
     else if(cNode->has_one_child()) 
     { 
      if(root->get_data().get_name() == data.get_name()) 
      { 
       if(cNode->get_right()!= NULL) 
       { 
        cNode->get_right()->set_parent(NULL); 
        root = cNode->get_right(); 
       } 
       else 
       { 
        cNode->get_left()->set_parent(NULL); 
        root = cNode->get_left(); 
       } 
      } 
      else if(cNode->get_right() != NULL) 
      { 
       cNode->get_right()->set_parent(cNode->get_parent()); 
       if(cNode->is_right_child()) 
       { 
        cNode->get_parent()->set_right(cNode->get_right()); 
       } 
       else 
       { 
        cNode->get_parent()->set_left(cNode->get_left()); 
       } 
      } 
      else 
      { 
       BTNode<value_type>* tempNode = find_min(cNode->get_right()); 
       value_type* tempStudent = new value_type (tempNode->get_data()); 
       remove(cNode->get_right(), tempNode->get_data()); 
       cNode->set_data(*tempStudent); 
      } 
      return true; 
     } 
     return false; 
    } 
} 

そして、再帰的に私のremove関数である50未満 のグレード値で任意のStudentオブジェクトを削除するために指定されてきました削除しようとしているので

Student::Student(std::string init_name) 
{ 
    name = init_name; 
    grade = rand() % 101; 
} 

のように構成されており、私の主な機能には、私は

を持っています

BSTree<Student>* student_tree = new BSTree<Student>; 
std::string studentName[]={"Adam", "Cameron", "Jackson", "KiSoon", "Nicholas", "Adrian", "Chris", "Jacob", "Lance", "Ryan", 
          "Alexander", "Damian", "James", "Liam", "Sang", "Andrew", "David", "Jared", "Madison", "Shane", "Ashley", "Dillon", 
          "Jodi", "Magdalena", "Simon", "Benjamin", "Dylan", "Jonathan", "Marcus", "Thomas", "Bradley", "Ethan", "Joshua", "Mark", 
          "Timothy", "Brobie", "Frederik", "Julius", "Melanie", "Trent", "Callan", "Hong", "Kelly", "Min", "Troy", "Callum", "Hugh", "Kenias", "Mitchell", "Zaanif"}; 

for (int i = 49; i > 0; i--) 
{ 
    int j = rand() % (i+1); 
    std::string tmp = studentName[j]; 
    studentName[j] = studentName[i]; 
    studentName[i] = tmp; 
} 

for (int i = 0; i < 50; i++) 
{ 
    Student student = Student(studentName[i]); 
    student_tree->insert(student, i); 
} 

cout << student_tree->printInOrder() << endl; 
//cout << "test" << endl; 
cout << "HD's: " << student_tree->hdCount() << endl; 
cout << "Average: " << student_tree->avg() << endl; 
student_tree->remove(); 

削除のパラメータとして何を渡すべきかわかりません。私はそれが50未満の学年の学生の名前であると仮定しますが、これらの名前をループして取得して関数呼び出しに入れる方法についてはわかりません。

編集：削除では、ノードの名前、渡されたデータ、ノードのグレード、およびデータが渡されるべきですか？すなわちif(data.get_name() > cNode->get_data().get_name())またはif(data.get_grade() > cNode->get_data().get_grade())

Answer 1

あなたの関数呼び出しのようで、パラメータは大丈夫です。

ただし、ツリーの特定のパスをトラバースするように選択しているようです。グレードが50未満のノードをすべて削除する場合は、次のようにツリー全体を反復処理する必要があります。 return remove（cNode-> get_left（）、data）|| （cNode-> get_right（）、data）を削除します。

これで、すでに正しい場合の基本ケースが得られます。 if（cNode == NULL） falseを返します。

次に、cNodeのグレードが50未満であるかどうかを確認します。そうであれば、それを削除してtrueを返します。

-Iを使用すると、レスポンスの