바이너리 트리 구현 : insert_tree () 관련 문제

우선이 구조 선언

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 함수 선언입니다.

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