二叉搜索树递归插入

Question

我目前有困难使用递归插入节点到二叉树。我几天前一直在讨论这个问题，并认为是时候我才找到答案！

Node类（.H）：

#ifndef STUDENT_MACROGUARD 
#define STUDENT_MACROGUARD 

#include <cstdlib> 
#include <string> 

namespace student_class 
{ 
    class student 
    { 
     public: 
      // Constructors/Destructors; 

      student(const float entry = 0, std::string name = "", 
         student* left_ptr = NULL, student* right_ptr = NULL); 
      ~student(void){}; 

      // Mutating member functions; 

      void set_grade(const float entry); 
      void set_name(std::string entry); 

      void set_left(student* node_ptr); 
      void set_right(student* node_ptr); 

      // Non mutating member functions; 

      float grade(void); 
      std::string name(void); 

      student* left(void); 
      student* right(void); 

      // Const member functions; 

      const student* left(void) const; 
      const student* right(void) const; 

    private: 
      std::string student_name; 
      float grade_field; 
      student* left_ptr; 
      student* right_ptr; 
    }; 
} 

#endif 

BSTree类来实现二叉树的数据结构（.H）：

#ifndef BTTree_MACROGUARD 
#define BTTree_MACROGUARD 

#include <cstdlib> 
#include <string> 
#include <iostream> 
#include "student.h" 

using namespace student_class; 

namespace BTTree_class 
{ 
class BTTree 
{ 
    public: 
      // Constructors/Destructors; 

      BTTree(student* node_ptr = NULL); 
      ~BTTree(void); 

      // Mutating member functions; 

      void insert(student* node_ptr = NULL, const float grade = 0, std::string name = ""); 
      void remove(student* node_ptr); 

      // Non mutating member functions; 

      student* grade_search(const float entry); 
      student* name_search(const std::string entry); 
      student* root(void); 
      void print_tree(student* node_ptr); 

      // Const member functions; 

      const student* grade_search(const float entry) const; 
      const student* name_search(const float entry) const; 
      const student* root(void) const; 

    private: 
      student* root_ptr; 
    }; 
} 

#endif 

我使用插入插入部件功能的实现到树中的节点：

void BTTree::insert(student* node_ptr, const float grade, std::string name) 
{ 
    if(root_ptr == NULL) 
    { 
     root_ptr = new student(grade, name); 
     return; 
    } 

    if(node_ptr == NULL) 
    { 
     node_ptr = new student(grade, name); 
     return; 
    } 
    else if(node_ptr->grade() > grade) 
    { 
     insert(node_ptr->left(), grade, name); 
    } 
    else 
    { 
     insert(node_ptr->right(), grade, name); 
    } 
} 

我不明白为什么这个插入不起作用。代码看起来完美无瑕，它让我挠了挠头。我写了一个使用迭代的替代插入函数，但递归是必须的。

任何帮助将是太棒了，谢谢。

Answer 1

的问题是在这里：

if(node_ptr == NULL) 
{ 
    node_ptr = new student(grade, name); 
    return; 
} 

node_ptr是一个局部变量，因为按值传递。因此，当您退出该功能时，分配会丢失。

要修复它 - 通过引用传递：

void BTTree::insert(student* &node_ptr, const float grade, std::string name) 

这将需要这些变化当然：

 student* & left(void); 
     student* & right(void);