二叉树中的随机零

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，根 - >数据在的“printf（”你好\ n“）线，这没有多大意义，我设置为零。任何帮助将不胜感激，让我知道如果你需要看到其他功能，我会编辑他们英寸

Answer 1

您的变量“root”设置为NULL，所以它不指向在第一次调用“insert”时分配的元素

编辑（后续评论） 根元素（您在“main”函数中分配的元素未初始化。必须

1）初始化它的元素（至少为NULL和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); 
    } 

第一，所以你添加的，而不是在根写第一个元素的新节点：在主要功能，你的根元素 所以在插入功能分配内存。

编辑：不要为main分配内存，并重写你的插入函数，所以它会得到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);