Использование двоичного дерева

Question

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

typedef struct node_{ 
    int val; 
    struct node_ *left; 
    struct node_ *right; 
}node; 

node* insert(node* root,int val); 
void inorder(node* root); 
int main(void) 
{ 
    int i; 
    int item; 
    node* root = NULL; 

    srand(time(NULL)); 

    for(i = 0; i < 10; i++) 
    { 
     item = rand()%15; 
     insert(root,item); 
    } 

    inorder(root); 

    return 0;  
} 

node* insert(node* root,int val) 
{ 
    if(root == NULL) 
    { 
     root = malloc(sizeof(node)); 
     if(root!= NULL) 
     { 
      (root)->val = val; 
      (root)->left = NULL; 
      (root)->right = NULL; 
     } 
     else 
      printf("%d not inserted. No memory available.\n",val); 
    } 
    else 
    { 
     if(val < (root)->val) 
     { 
      insert((root->left),val); 
     } 

     if(val>root->val) 
     { 
      insert(((root)->right),val); 
     } 
    } 
} 

void inorder(node* root) 
{ 
    printf("%p",root); 
    if(root != NULL) 
    { 
     inorder(root->left); 
     printf("%3d",root->val); 
     inorder(root->right); 
    } 
} 

Я пытаюсь создать двоичное дерево и распечатать значения в порядке. Однако, когда я запускаю этот код, printf адреса печатает нуль, что явно означает, что мое дерево пуст, поэтому printf и рекурсия ниже не выполняются. Я не могу понять, где я поступил неправильно, любые предложения или ответы были бы оценены, потому что я не могу понять, почему корень был бы нулевым после вызова всех этих вставок в главном.

Answer 1

Вы передаете root в качестве параметра insert() (в котором говорится, что он что-то вернет, но не делает). Внутри insert вы получите malloc ваш узел и назначьте его локальной переменной root. Ничто из того, что вы когда-либо делали, делает его вне функции insert.

Попробуйте что-то вернуть с insert или с помощью глобальной сети root.

Как @JoshuaByer намекает на комментарии ниже, другой подход заключается в том, чтобы сделать ваш метод insert «пройденным по ссылке», чтобы он мог эффективно модифицировать то, что ему было передано.

void insert(node** rootp,int val) 
{ 
    if(*rootp == NULL) 
    { 
     *rootp = malloc(sizeof(node)); 
    } 
    /* and so on */ 

Если вы не понимаете, что это говорит, Google «Передавать по ссылке в C», и я уверен, вы получите полезную информацию.

Answer 2

В main() после объявления и инициализации корня (node* root = NULL;) вы никогда не назначаете его. Чтобы исправить это, вы должны, вероятно, изменить lin insert(root,item); на root = insert(root,item);.

Также обратите внимание, что хотя insert определяется как возвращаемый node *, он не возвращает никакого значения.