Случайный ноль в двоичном дереве

Question

Я столкнулся с проблемой с простой программой обработки двоичных деревьев. В коде вводится нуль, и я просто не могу понять, как избавиться от него. Вот главная функция в программе:

//-------------------------Structure definition---------------------------------------------------------------------------------- 
struct tree { 
    int data; 
    struct tree *left; 
    struct tree *right; 
}; 


//-------------------------Function definitions-------------------------------------------------------------------------------- 
int traverse(struct tree *root); 
struct tree * insert(struct tree *root, int num); 
int search(struct tree *root, int num); 
int maxdepth(struct tree *root); 
void help(); 


//-------------------------Help function to display commands---------------------------------------------------------- 
void help() 
{ 
    printf("\n Q to quit program. \n"); 
    printf(" # to insert # into the list. \n"); 
    printf(" s # to search for # in the list. \n"); 
    printf(" d # to delete # from list. \n"); 
    printf(" p to print the entire list. \n"); 
    printf(" ? to view this message again. \n\n"); 
} 


//-------------------------Traverse (print)-------------------------------------------------------------------------------------- 
int traverse(struct tree *root) 
{ 
    if(root==NULL) 
    { 
     return 0; 
    } 
    traverse(root->left); 
    printf("%d ", root->data); 
    traverse(root->right); 
} 


//-------------------------Insert function to sort and insert user input ---------------------------------------------- 
struct tree * insert(struct tree *root, int num) 
{ 
    if(root==NULL) 
    { 
     root=malloc(sizeof(struct tree)); 
     root->data = num; 
     root->left = root->right=NULL; 
     return(root); 
    } 
    if(num > root->data) 
    { 
     root->right=insert(root->right, num); 
     return(root); 
    } 
    if(num < root->data) 
    { 
     root->left=insert(root->left, num); 
     return(root); 
    } 
    if(num==root->data) 
    { 
     return (root); 
    } 
} 


//-------------------------Search function. Just returns a 1/0 for yes/no ------------------------------------------ 
int search(struct tree *root, int num) 
{ 
    if(root==NULL)return(0); 
    if(num==root->data)return(1); 
    if(1==search(root->left, num) || 1==search(root->right, num)) 
    { 
     return(1); 
    } 
    else 
    { 
     return(0); 
    } 
} 


//------------------------MaxDepth function to calculate the depth of the tree -------------------------------- 
int maxdepth(struct tree *root) 
{ 
    int ldepth; 
    int rdepth; 
    if(root==NULL) 
    { 
     return 0; 
    } 
    else 
    { 
     ldepth=maxdepth(root->left); 
     rdepth=maxdepth(root->right); 
     if(ldepth > rdepth) 
      return ldepth+1; 
     else 
      return rdepth+1; 
    } 
} 

//-------------------------Main! -------------------------------------------------------------------------------------------------- 
int main(void) 
{ 
    struct tree *root; 
    char buffer[120]; //Temp storage 
    int num; //User input will move from buffer to here. 
    int searchVal; 

//Memory Allocations block. 
    root=malloc(sizeof(struct tree));  


    printf("Hello. \n"); 
    while(1==1) 
    { 
     printf("> "); 

     fgets(buffer, sizeof(buffer), stdin); 

     switch(buffer[0]) 
     { 
      case '0': 
      case '1': 
      case '2': 
      case '3': 
      case '4': 
      case '5': 
      case '6': 
      case '7': 
      case '8': 
      case '9': 
       if(1==(sscanf(buffer, "%d", &num))){ 
        insert(root, num); 
        } 
       break; 

      case 's': 
       if(1==(sscanf(buffer, "s %d", &num))){ 
        searchVal=search(root, num); 
        if(1==search(root, num)){ 
         printf("That number is in the list. \n"); 
        }else{ 
         printf("That number is not in the list. \n"); 
        } 
       } 
       break; 


      case 'p': 
       traverse(root); 
       printf("\n Tree depth: %d \n", maxdepth(root)); 
       break; 

      case '?': 
       help(); 
       break; 

      case 'q': 
      case 'Q': 
       exit(0); 
       break; 

      default: 
       help(); 
       break; 

      } 
    } 
} 

Согласно GDB, корне-> данных устанавливается в нуль в «Е (» Hello \ п ") линия, которая не имеет большого смысла для меня. Любая помощь будет оценена, дайте мне знать, если вам нужно увидеть другие функции, и я их отредактирую. Спасибо заранее.

Answer 1

Ваша переменная «root» установлена ​​в NULL, поэтому она не указывает на элемент, выделенный при первом вызове «вставить».

EDIT (комментарий к комментарию) Корневой элемент (тот, который вы назначаете в «основной» функции, не инициализирован. должны

1) инициализировать свои элементы (слева и справа до NULL, как минимум) 2) поместить самое первое значение в поле данных.

«0» - это поле этого элемента.

Answer 2

//Memory Allocations block. 
root=malloc(sizeof(struct tree)); 
root=NULL; 

Не устанавливайте в NULL после выделения памяти.

Answer 3

Ваша проблема в первой вставке. В основной функции, вы выделяете память для корневого элемента так в функции вставки:

struct tree * insert(struct tree *root, int num) 
{ 
    if(root==0) 
    { 
     root=malloc(sizeof(struct tree)); 
     root->data = num; 
     root->left = root->right=0; 
     return(root); 
    } 
    if(num > root->data) 
    { 
     root->right=insert(root->right, num); 
     return(root); 
    } 

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

Редактировать: не выделяют память для корня в главном и переписывают вашу функцию вставки, чтобы она получала struct tree** root. что-то вроде этого:

struct tree * insert(struct tree** root, int num) 
{ 
     if(*root==NULL) 
     { 
      *root=malloc(sizeof(struct tree)); 
      (*root)->data = num; 
      (*root)->left = (*root)->right=0; 
      return(*root); 
     ......... 

и ссылаться на него как то

root = NULL; 
....... 
insert(&root, num);