Реализация двоичного дерева: проблемы с insert_tree () - PullRequest
Новая
       83

Реализация двоичного дерева: проблемы с insert_tree ()

2 голосов
/ 09 мая 2020

Я начинаю изучать немного 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 выполняет mallo c и правильно распределяет память, поэтому он выводит 30 внутри insert_tree, но когда я вызываю printTree(), в дереве нет узлов. Я не знаю почему, поскольку я передаю левый указатель узла, и он должен быть безопасным из контекста insert_tree.

В чем проблема с insert_tree() здесь?

Ответы [ 2 ]

3 голосов
/ 09 мая 2020

Для начала, это объявление структуры 

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 получает указатель на узел root по значению. То есть функция имеет дело с копией исходного указателя, поэтому изменение копии исходного указателя внутри функции не влияет на значение исходного указателя.

Вам нужно передать указатель по ссылке. В C передача по ссылке означает передачу объекта косвенно через указатель. Учтите, что при выделении памяти может произойти сбой. Желательно, чтобы функция сообщала об успешности вставки нового узла.

Также будет более грамотно сделать первый параметр указателем на указатель на узел root, а второй параметр - значение, которое должно быть вставлено.

В любом случае это объявление функции 

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
0 голосов
/ 09 мая 2020

Вы должны передать 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);

Таким образом вы гарантируете, что любые изменения, внесенные в переменную внутри функции, сохранятся. Это происходит потому, что, когда вы вместо этого передаете значение по значению, функция создает копию переменной, которую вы добавили в качестве параметра, и, таким образом, любые ее изменения не повлияют на исходное значение.

edit: Чтобы уточнить, указатели по-прежнему являются переменными, и как переменные они содержат значение. Чтобы изменить значение переменной в функции, вам нужно получить ее адрес, адрес указателя, как и любой другой адрес переменной, доступен через &. Если Root (переменная, которую вы объявили в main) не была указателем, вы также могли бы использовать обычный struct Node * root в качестве параметра, но поскольку это не так, вам следует придерживаться struct Node ** root.

...