二叉树实现：insert_tree() 的问题

Question

在学习了 C++ 之后，我开始学习一点点 C，所以我正在使用二进制树实现。

代码：

struct Node {
    int value = -1;
    struct Node* left = NULL;
    struct Node* right = NULL;
};

void insert_tree(int value, Node* root) {
    if (root == NULL) {
        root = (struct Node*) malloc(sizeof(Node));
        root->value = value;
        printf("%d\n", root->value);
        root->left = NULL;
        root->right = NULL;
    }
    else {
        if (root->value >= value) {
            insert_tree(value, root->left);
        }
        else {
            insert_tree(value, root->right);
        }
    }
}

void printTree(Node* root) {
    if (root != NULL) {
        printf("%i\n", root->value);
        printTree(root->left);
        printTree(root->right);
    }
}

int main() {
    Node* root = NULL;
    insert_tree(30, root);
    printTree(root);
}

在这里我可以看到 insert_tree 是如何执行 malloc 并正确分配内存的，因此它在 insert_tree 中输出 30，但是当我调用 printTree() 时没有节点在树上。我不知道为什么，因为我正在传递节点的左指针，并且它应该在 insert_tree.

的上下文中是安全的

这里insert_tree()有什么问题？

Answer 1

你应该通过引用传递 root ，改变这个：

void insert_tree(int value, Node* root) {
    if (root == NULL) {
        root = (struct Node*) malloc(sizeof(Node));
        root->value = value;
        printf("%d\n", root->value);
        root->left = NULL;
        root->right = NULL;
    }
    else {
        if (root->value >= value) {
            insert_tree(value, root->left);
        }
        else {
            insert_tree(value, root->right);
        }
    }
}

对此：

void insert_tree(int value, Node** rootp) {
    struct Node * root = *rootp;
    if (root == NULL) {
        root = (struct Node*) malloc(sizeof(Node));
        root->value = value;
        printf("%d\n", root->value);
        root->left = NULL;
        root->right = NULL;
    }
    else {
        if (root->value >= value) {
            insert_tree(value, &root->left);
        }
        else {
            insert_tree(value, &root->right);
        }
    }
}

然后像这样调用插入：

insert_tree(value , &root);

这样您可以确保在函数内对变量所做的任何更改都得到保留。发生这种情况是因为当您改为按值传递时，该函数会创建您作为参数添加的变量的副本，因此对其进行的任何更改都不会影响原始值。

编辑：澄清一下，指针仍然是变量，并且作为变量，它们拥有一个值。为了在函数中更改变量的值，您需要获取其地址，指针的地址就像通过 & 访问任何其他变量的地址一样。如果 Root（您在 main 中声明的变量）不是指针，那么您也可以使用普通的 struct Node * root 作为参数，但由于它不是，您应该坚持使用 struct Node ** root.

Answer 2

对于初学者这个结构声明

struct Node {
    int value = -1;
    struct Node* left = NULL;
    struct Node* right = NULL;
};

在 C 中无效。您不能指定初始值设定项。

所以声明应该像

struct Node {
    int value;
    struct Node* left;
    struct Node* right;
};

函数insert_tree按值获取指向根节点的指针。即函数处理原始指针的副本，因此在函数内更改原始指针的副本不会影响原始指针的值。

您需要通过引用传递指针。在 C 中，按引用传递意味着通过指针间接传递对象。考虑到内存分配可能会失败。希望该函数能够报告新节点的插入是否成功。

另外，将第一个参数设为指向根节点的指针，将第二个参数设为应插入的值会更胜任。

无论如何这个函数声明

void insert_tree(int value, Node* root) {
                            ^^^^^^^^^^

是无效的 C 函数声明，因为在 C 中与 C++ 相反，您必须将关键字 struct 指定为

void insert_tree(int value, struct Node* root) {
                            ^^^^^^^^^^^^^^^^^

递归函数insert_tree可以这样定义

int insert_tree( struct Node **root, int value ) 
{
    if ( *root == NULL ) 
    {
        *root = (struct Node*) malloc( sizeof( struct Node ) );
        if ( *root != NULL )
        {
            ( *root )->value = value;
            ( *root )->left  = NULL;
            ( *root )->right = NULL;
        }

        return *root != NULL;
    }
    else 
    {
        if ( value < ( *root )->value ) 
        {
            return insert_tree( &( *root )->left, value );
        }
        else 
        {
            return insert_tree( &( *root )->right, value );
        }
    }
}

而且函数可以这样调用

int main( void ) 
{
    struct Node *root = NULL;
    insert_tree( &root, 30 );
    printTree( root );
}

此外，由于函数 printTree 不会更改树，因此其参数应具有限定符 const.

void printTree( const struct Node* root ) {
    if (root != NULL) {
        printf("%i\n", root->value);
        printTree(root->left);
        printTree(root->right);
    }
}

这是一个演示 C 程序。

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

struct Node 
{
    int value;
    struct Node *left;
    struct Node *right;
};

int insert_tree( struct Node **root, int value ) 
{
    if ( *root == NULL ) 
    {
        *root = (struct Node*) malloc( sizeof( struct Node ) );
        if ( *root != NULL )
        {
            ( *root )->value = value;
            ( *root )->left  = NULL;
            ( *root )->right = NULL;
        }

        return *root != NULL;
    }
    else 
    {
        if ( value < ( *root )->value ) 
        {
            return insert_tree( &( *root )->left, value );
        }
        else 
        {
            return insert_tree( &( *root )->right, value );
        }
    }
}

void printTree( const struct Node* root ) {
    if (root != NULL) {
        printf("%i\n", root->value);
        printTree(root->left);
        printTree(root->right);
    }
}

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

    const int N = 10;

    srand( ( unsigned int )time( NULL ) );

    for ( int i = 0; i < N; i++ )
    {
        insert_tree( &root, rand() % N );
    }

    printTree( root );

    return 0;
}

它的输出可能看起来像

二叉树实现：insert_tree() 的问题

Binary Tree implementation: issues with insert_tree()

c

struct

pointers

pass-by-reference

binary-search-tree