二叉搜索树创建

Question

我已经编写了一个简单的代码来创建元素并将其插入到二叉搜索树中，当我按照以下方式编写代码时，链接似乎没有发生，任何人都可以帮助我理解到底发生了什么在插入函数中？我知道将元素插入二叉搜索树的代码，只是想知道为什么这个不起作用。

#include <stdio.h>
#include<stdlib.h>

struct node {
    struct node *left;
    struct node* right;
    int element;
};

void insert(struct node *node,int x) {
    if(node==NULL) {
        node=(struct node *)malloc(sizeof(struct node));
        node->element=x;
        node->left=NULL;
        node->right=NULL;
    } else {
        if(x<node->element) {
            insert(node->left,x);}
        else {
            insert(node->right,x);
        }
    }
}

void inorder(struct node *base) {
    if(base!=NULL) {
        inorder(base->left);
        printf("%d ",base->element);
        inorder(base->right);
    }
}


int main(int argc, char *argv[]) {
    struct node *base;
    base=(struct node *)malloc(sizeof(struct node));
    base->element=1;
    base->left=NULL;
    base->right=NULL;
    insert(base,25);
    insert(base,30);
    inorder(base);

    return 0;
}

如果插入函数这样写，它可以工作，但对于创建二叉搜索树的第一个节点仍然不起作用，困惑:/

void insert2(struct node *node,int x) {
    if(node==NULL) {
        node=(struct node *)malloc(sizeof(struct node));
        node->element=x;
        node->left=NULL;
        node->right=NULL;
    } else {
        if(x<node->element) {
            if(node->left==NULL) {
                node->left=(struct node *)malloc(sizeof(struct node));
                node->left->element=x;
                node->left->left=NULL;
                node->left->right=NULL;
            } else {
                insert2(node->left,x);
            }
        } else {
            if(node->right==NULL) {
                node->right=(struct node *)malloc(sizeof(struct node));
                node->right->element=x;
                node->right->left=NULL;
                node->right->right=NULL;
            } else {
                insert2(node->right,x);
            }
        }
    }
}

Answer 1

当您将值传递给 C 中的函数时，您使用的是按值传递。这意味着该值被复制到另一个变量中，该变量成为函数的局部变量。

void change(struct node *n) {
    n = 42;
}

int main(void) {
    change(NULL); // change can't change the value of NULL, can it?
}

现在看看你的insert函数...假设我调用insert(NULL,42);，你认为insert试图改变NULL吗？或者它是否试图更改一些您的 main 函数看不到的局部变量？

您已经知道需要做什么了...按照您在评论中的建议，让您的 insert 函数使用额外的指针间接级别，或者 return 根节点来自 insert，以便您可以将 insert 所做的更改传播到存储在 main 中的数据结构中（使用赋值 = 运算符）。

Answer 2

C 是按值传递。当您将某些内容传递给函数的参数时，该函数会复制它。因此，当您将 struct node pointer 传递给 insert 函数时，C 会复制该指针。

你在 main 中做的是首先你做了一个 struct node* base:

base --> struct node.

当你调用insert(base, 25)时，C会复制一个base。所以现在在你的记忆中你有这样的东西：

basecpy ---> [struct node] <--- base

所以在你的 insert 中，你实际上是在做

if(basecpy==NULL)
    {basecpy=(struct node *)malloc(sizeof(struct node));
    basecpy->element=x;
    basecpy->left=NULL;
    basecpy->right=NULL;}

根本不会改变 base - 它只是改变 basecpy.

这个可以用双指针解决：

void insert(struct node **node, int x) {
    if (*node == NULL) {
        *node = malloc(sizeof(*node));
        (*node)->element=x;
        (*node)->left=NULL;
        (*node)->right=NULL;
    } else {
        if (x < (*node)->element) {
            insert(&((*node)->left), x);
        } else {
            insert(&((*node)->right), x);
        }
    }
}

然后要使用它，传入base的地址。

insert(&base, 25);

指针可能很棘手 :)

ideone

二叉搜索树创建

BINARY SEARCH TREE creation

c

binary-search-tree