在二叉搜索樹中刪除多個節點

Question

我不太清楚如何刪除二叉搜索樹中的節點。我已經規定，以消除任何Student對象小於50 一個檔次值這是我的刪除功能

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

，並遞歸與

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

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） return false;

然後您將檢查cNode的等級是否小於50.如果是，請將其刪除並返回true。

-I我假設你有一個學生，以及在每個節點