二叉樹中的隨機零

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);