如何在BST插入中进行修复，让插入功能发挥作用

Question

在Visual Studio中显示的代码InsertBSTNode函数是错误的。但我不知道如何解决。要求是不要改变函数的类型。

TreeNode

 class TreeNode{   
    public:
    int data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x): data(x), left(NULL), right(NULL){}
    };

InsertBSTNode

void InsertBSTNode(TreeNode* &root, int val){
// Input your code here.
if (root==NULL){
    root->data=val;
    root->left=root->right=NULL;}
else if(val<root->data)
    root->left=InsertBSTNode(root->left,val);//error
else if(val>root->data)
    root->right=InsertBSTNode(root->right,val);//error
return root;//error

};

Answer 1

所以这是我认为你想写的代码。

void InsertBSTNode(TreeNode* &root, int val) {
    if (root == NULL) {
        root = new TreeNode;
        root->data=val;
        root->left=root->right=NULL;
    }
    else if (val<root->data)
        InsertBSTNode(root->left,val);
    else
        InsertBSTNode(root->right,val);
}

我已经修复了无效使用返回值的问题，并且在做插入的地方分配了一个节点，修复了NULL指针错误。

Answer 2

这就是问题的解决方法。谢谢@john的帮助!

void InsertBSTNode(TreeNode* &root, int val){
if (root==NULL){
    root = new TreeNode(val);
    root->data=val;
    root->left=root->right=NULL;}
else if(val<root->data)
    InsertBSTNode(root->left,val);
else if(val>root->data)
    InsertBSTNode(root->right,val);
};