时间戳

首页 > 解决方案 > 如何在C中将新节点插入二叉树？

c - 如何在C中将新节点插入二叉树？

问题描述

我一直试图让它工作一段时间，但显然有一些我不明白的东西。

我必须将一个新节点插入到二叉树中，并将“电话”作为它的值。

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)

标签： ctreebinary-treebinary-search-treebinary-search

解决方案

对于初学者来说，有一个错字

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。

推荐阅读