如何在C语言的二叉树中插入新节点？

Question

我一直在尝试使它工作一段时间，但显然有些我不理解。

我必须将一个新节点插入一个以“ phone”为值的二叉树中。

void bst_insert_node(bstree* bst, unsigned long phone, char *name) {
    bst_node* new_node = malloc(sizeof(bst_node));
    new_node->phone = phone;
    bst_node* y = NULL;
    bst_node* x = bst->root;

    while(x != NULL)
    {
        y = x;
        if(phone <= x->phone)
             x = x->left;
        else x = x->right;
    }
    if (y == NULL)
    {
        bst->root = new_node;
    }
    else
    {
        if (phone <= y->phone)
             y->left->phone = phone;
        else y->right->phone = phone;
    }
}

我将不胜感激任何类型的评论和解释。

非常感谢。

编辑：我已将y-> left-> phone = phone纠正为y-> left = new_node，作为您的建议之一。仍然，它不起作用。Valgrind给我这个：

valgrind ./a.out telefonbuch_einfach.txt ==5941== Memcheck, a memory error detector
==5941== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5941== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==5941== Command: ./a.out telefonbuch_einfach.txt
==5941== 
==5941== error calling PR_SET_PTRACER, vgdb might block
==5941== Conditional jump or move depends on uninitialised value(s)
==5941==    at 0x4013AB: bst_insert_node (introprog_telefonbuch.c:19)
==5941==    by 0x400A5E: read_file (introprog_main_telefonbuch.c:54)
==5941==    by 0x400CB6: main (introprog_main_telefonbuch.c:119)
==5941== 
==5941== Use of uninitialised value of size 8
==5941==    at 0x401435: bst_insert_node (introprog_telefonbuch.c:31)
==5941==    by 0x400A5E: read_file (introprog_main_telefonbuch.c:54)
==5941==    by 0x400CB6: main (introprog_main_telefonbuch.c:119)
==5941== 
==5941== Invalid write of size 8
==5941==    at 0x401435: bst_insert_node (introprog_telefonbuch.c:31)
==5941==    by 0x400A5E: read_file (introprog_main_telefonbuch.c:54)
==5941==    by 0x400CB6: main (introprog_main_telefonbuch.c:119)
==5941==  Address 0x18 is not stack'd, malloc'd or (recently) free'd
==5941== 
==5941== 
==5941== Process terminating with default action of signal 11 (SIGSEGV)
==5941==  Access not within mapped region at address 0x18
==5941==    at 0x401435: bst_insert_node (introprog_telefonbuch.c:31)
==5941==    by 0x400A5E: read_file (introprog_main_telefonbuch.c:54)
==5941==    by 0x400CB6: main (introprog_main_telefonbuch.c:119)
==5941==  If you believe this happened as a result of a stack
==5941==  overflow in your program's main thread (unlikely but
==5941==  possible), you can try to increase the size of the
==5941==  main thread stack using the --main-stacksize= flag.
==5941==  The main thread stack size used in this run was 8388608.
==5941== 
==5941== HEAP SUMMARY:
==5941==     in use at exit: 832 bytes in 6 blocks
==5941==   total heap usage: 7 allocs, 1 frees, 4,928 bytes allocated
==5941== 
==5941== LEAK SUMMARY:
==5941==    definitely lost: 0 bytes in 0 blocks
==5941==    indirectly lost: 0 bytes in 0 blocks
==5941==      possibly lost: 0 bytes in 0 blocks
==5941==    still reachable: 832 bytes in 6 blocks
==5941==         suppressed: 0 bytes in 0 blocks
==5941== Rerun with --leak-check=full to see details of leaked memory
==5941== 
==5941== For counts of detected and suppressed errors, rerun with: -v
==5941== Use --track-origins=yes to see where uninitialised values come from
==5941== ERROR SUMMARY: 5 errors from 3 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)

Answer 1

您搜索要插入的正确节点很好。问题是：

• 分配新节点时，忽略将左右设置为NULL。这些将具有垃圾值。
• 找到节点后，您尝试仅将电话号码分配给这些垃圾值。您需要分配新创建的节点。

void bst_insert_node(bstree* bst, unsigned long phone, char *name) {
    // Use calloc, memset, or manually set all values to NULL
    bst_node* new_node = malloc(sizeof(bst_node));
    // TODO: verify new_node is not NULL
    new_node->phone = phone;
    new_node->left = NULL;
    new_node->right = NULL;
    new_node->name = NULL;  // TODO: use strdup to copy name

    bst_node* y = NULL;
    bst_node* x = bst->root;

    while(x != NULL)
    {
        y = x;
        if(phone <= x->phone)
             x = x->left;
        else x = x->right;
    }
    if (y == NULL)
    {
        bst->root = new_node;
    }
    else
    {
        if (phone <= y->phone)
             y->left = new_node;
        else
            y->right = new_node;
    }
}

Answer 2

对于初学者来说有错字

else
{
    if (phone <= y->phone)
         y->left->phone = phone;
    else y->right->phone = phone;
}

应该有

else
{
    if (phone <= y->phone)
         y->left = new_node;
    else y->right = new_node;
}

该功能不使用参数name。

也未为新创建的节点初始化数据成员left和right。

可以通过以下方式定义功能，如下所示。我假设定义了相应的结构，如

typedef struct bst_node
{
    unsigned long phone;
    char *name;
    struct bst_node *left;
    struct bst_node *right;
} bst_node;

typedef struct
{
    bst_node *root;
} bstree;

这里是功能。

int bst_insert_node( bstree* bst, unsigned long phone, const char *name ) 
{
    bst_node *new_node = malloc( sizeof( bst_node ) );
    int success = new_node != NULL;

    if ( success )
    {
        new_node->name = malloc( strlen( name ) + 1 );

        success = new_node->name != NULL;

        if ( !success ) free( new_node );
    }

    if ( success )
    {
        strcpy( new_node->name, name );
        new_node->phone = phone;
        new_node->left = NULL;
        new_node->right = NULL;

        bst_node **current = &bst->root;

        while ( *current != NULL )
        {
            if ( new_node->phone < ( *current )->phone )
            {
                current = &( *current )->left;
            }
            else
            {
                current = &( *current )->right;
            }
        }

        *current = new_node;
    }

    return success;
}       

如果数据成员名称是一个字符数组，则该函数将看起来更简单，因为您无需分配内存来存储name。