c - 二叉树实现: issues with insert_tree()

Question

在学完 C++ 后，我开始学习一点 C 语言，所以我使用了 bintree 实现。

代码:

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

对于初学者来说，这个结构声明

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;
}

它的输出可能看起来像

1
0
9
4
3
7
5
6
5
8