使用递归在 bst 中插入元素

Question

我正在尝试添加用户在 BST.For 中输入的元素，我使用了 2 个函数，一个用于创建函数，另一个仅用于将元素插入到树中。一个是预购函数，用于检查插入是否完成最初我尝试添加元素 manually.Its 不打印所有插入的值。

整体布局

struct Node{
int data;
struct Node* left;
struct Node* right;
};
void Inorder(struct Node* root){
if(root==NULL){
 return;
}
else{
 Inorder(root->left);
 cout<<root->data<<" ";
 Inorder(root->right);
  }
}
struct Node* create_node(int data){
    struct Node* node=(struct Node*) malloc(sizeof(struct Node));
    node->data=data;
    node->left=NULL;
    node->right=NULL;
    return node;
}

问题代码：-

struct Node* insert(struct Node* root,int data){
    static struct Node* prev=NULL;
    if(root==NULL && prev==NULL){
        return create_node(data);
    }
    if(root->data==data){
        return root;
    }
    else{
        if(root==NULL){
            struct Node* ptr=create_node(data);
            if(prev->data>data){
                prev->left=ptr;
                return root;
            }
            else{
                prev->right=ptr;
                return root;
            }
        }
        else{
            if(root->data>data){
               prev=root;
                insert(root->left,data);
                
            }
            else{
               prev=root;
                insert(root->right,data);
                 
            }
        }
    }
}

主要

int main()
{
    struct Node* root=NULL;
    root=insert(root,5);
    Inorder(root);
    cout<<endl;
    insert(root,3);
    Inorder(root);
     insert(root,10);
    Inorder(root);
    return 0;
}

有一件事我注意到，一旦我们调用 insert 插入下一个元素（此处为 3），prev 是静态的，它不会再次从头开始滚动，因为它被声明 static.To 克服了这一点每次我在main()中调用insert函数时，尝试通过将prev设为全局并在main中设为null来优化问题代码，优化后的代码如下：

#include <iostream>
#include<stdlib.h>
using namespace std;
static struct Node* prev=NULL;
struct Node{
  int data;
  struct Node* left;
  struct Node* right;
};
void Inorder(struct Node* root){
    if(root==NULL){
        return;
    }
    else{
        Inorder(root->left);
        cout<<root->data<<" ";
        Inorder(root->right);
    }
}
struct Node* create_node(int data){
    struct Node* node=(struct Node*) malloc(sizeof(struct Node));
    node->data=data;
    node->left=NULL;
    node->right=NULL;
    return node;
}
struct Node* insert(struct Node* root,int data){
    if(root==NULL && ::prev==NULL){
        return create_node(data);
    }
    if(root->data==data){
        return root;
    }
    else{
        if(root==NULL){
            struct Node* ptr=create_node(data);
            if(::prev->data>data){
                ::prev->left=ptr;
                return root;
            }
            else{
                ::prev->right=ptr;
                return root;
            }
        }
        else{
            if(root->data>data){
               ::prev=root;
                insert(root->left,data);
                
            }
            else{
               ::prev=root;
                insert(root->right,data);
                 
            }
        }
    }
}
int main()
{
    struct Node* root=NULL;
    root=insert(root,5);
    Inorder(root);
    cout<<endl;
    ::prev=NULL;
    insert(root,3);
    Inorder(root);
    ::prev=NULL;
     insert(root,10);
    Inorder(root);
       

    return 0;
}

Answer 1

这不是插入 BST 的工作方式。您根本不需要 prev 指针。

您的代码中的一个问题是您没有使用递归调用的 return 值，它在某些时候将成为指向新节点的指针！您真的应该将该 return 值分配给当前节点的 left 或 right 成员。

此外，以下 if 条件永远不会成立，因为此时已经保证 root 不是 NULL:

else{
    if(root==NULL){

正确的代码其实很简单：

struct Node* insert(struct Node* root, int data){
    if (root == NULL) {
        root = create_node(data);
    } else if (root->data > data) {
        root->left = insert(root->left, data);
    } else if (root->data < data) {
        root->right = insert(root->right, data);
    }
    return root;
}

我还会在您的主代码的输出中添加一些换行符：

int main()
{
    struct Node* root = NULL;

    root = insert(root, 5);
    Inorder(root);
    cout << endl;

    insert(root, 3);
    Inorder(root);
    cout << endl;

    insert(root, 10);
    Inorder(root);
    cout << endl;

    return 0;
}

Answer 2

我在代码中注意到的问题（遗憾的是无法上传代码段）。在下面提到的部分。

if(root->data==data){
        return root;
    }

首先让我解释一下递归函数，开始时根在插入时为空（这里插入5作为根）所以第一个条件将被满足即

if(root==NULL && ::prev==NULL){
        return create_node(data);
    }

而函数会return，现在我将全局变量prev设置为NULL，因为我想从树的根部再次遍历以添加下一个元素。

现在，一旦我们尝试添加另一个元素（此处添加元素 3）。这个条件

if(root==NULL && ::prev==NULL){
        return create_node(data);
    }

不会是真的，现在编写逻辑时的思考过程正在检查是否在某个阶段向下遍历树时是否遇到具有相同值的节点然后我们将 return 根节点并终止功能。这就是我试图实现的。这是代码，如果你能联系起来（问题代码片段）

else if(root->data==data){
        return root;
    }

毫无疑问，方法是好的，但我忘了添加一个条件（实际上我在这个阶段抢占了根不会是NULL）但是根可以是NULL。因此，我们将面临分段错误（在调试器模式下 -> 这帮助我找到了代码中的错误！）。
所以正确的代码是：

else if(root && root->data==data){// or if(root!=NULL && root->data=data)
        return root;
    }

其余代码保持不变

所以总结一下，当遍历树时，我们 return 所有条件都为真，一旦我们达到 NULL，那么由于第一个条件我们不会满足 prev!=NULL，所以它来到下一个条件 root->data==data 但这里 root=NULL 所以我们得到 分段错误 并且函数永远不会遇到 ROOT==NULL ，它只是为此目的而设计的，即树中的 add/insert 元素作为遍历树时一切似乎都很好。所以为了解决这个问题，我修改了 else if 条件，即 else if(root && root->data==data)

所以完整的功能代码如下：

struct Node* insert(struct Node* root,int data){
    if(root==NULL && ::prev==NULL){
        return create_node(data);
    }
    else if(root && root->data==data){
        return root;
    }
    else{
        if(root==NULL){
            struct Node* ptr=create_node(data);
            if(::prev->data>data){
                ::prev->left=ptr;
                return root;
            }

            else{
                ::prev->right=ptr;
                return root;
            }
        }
        else{
            if(root->data>data){
               ::prev=root;
                insert(root->left,data);
                
            }
            else{
               ::prev=root;
                insert(root->right,data);
                 
            }
        }
    }
}

PS：对包括问题中提到的一棵树在内的许多树执行了代码，并获得了预期的结果，即 Inorder 是一个排序数组，表明插入已正确完成。

使用递归在 bst 中插入元素

Inserting elements in a bst using recursion

c++

recursion

binary-search-tree

data-structures