樹不會超出大小3

我試圖在二叉搜索樹中實現插入子例程，其中每個節點都有一個字（字符串）作爲鍵。我從STDIN中取詞並使用插入功能插入它們。但是每當我進行遍歷時，我都會發現樹不會超過3個節點。什麼可能是錯誤的？我的代碼是在這裏附：樹不會超出大小3

typedef struct treenode 
{ 
    char word[20];    //word is the key for each node 
    struct treenode *left; 
    struct treenode *right; 

} treenode; 



treenode *insert (treenode *node, char *word) 
{ 
    if(node==NULL)      //if a null node is reached,make a temp node and append it 
    { 
    treenode *temp; 
    temp = (treenode *) malloc(sizeof(treenode)); 
    strcpy (temp ->word,word); 
    temp-> left = NULL; 
    temp-> right = NULL; 
    return temp; 
    } 


    if ((strcmp(word, node ->word)>0)) //if the key is greater than node.word,go to right child 
    { 
     node-> right = insert(node-> right, word); 
    } 
    else if(strcmp(word,node->word)<=0) //if key <node.word,go to left child 
    { 
     node-> left = insert(node-> left, word); 
    } 

} 

void printinorder(treenode *node) 
{ 

    if(node == NULL) return; 
    printinorder(node-> left); 
    printf("%s ",node-> word); 
    printinorder(node-> right); 

} 



int main() 
{ 
    treenode *root = NULL; 
    char string[20]; 
    scanf("%s",string); //first input is taken once here and once again inside loop,but its OK 
    root = insert(root, string+1); //duplicate entries are also stored 

    while(strcmp(string,".")!=0) //input is terminated by a full stop 
    { 
     insert(root, string+1); 
     scanf("%s",string); 
    } 


    printinorder(root);   //finally printing the BST 
    return 0; 
}

來源

2014-10-11 Aahitagni Mukherjee

你可能想要回到這個東西的底部。並[避免在C程序中投射malloc]（http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc）。 – WhozCraig 2014-10-11 05:48:28

嘗試調試器並查看'* insert（）'。 – user1336087 2014-10-11 05:49:03

@WhozCraig謝謝，返回工作。 – 2014-10-11 06:06:31

與實現的問題是，你正試圖將create_node和insert合併成一個單一的功能，然後使用該單一功能作爲一個放之四海而皆準的解決辦法用於樹的初始化和插入。這在insert返回類型（如註釋中所述）導致併發症，並可能導致您錯過insert所需的遞歸。（注添加和insert一個else下兩個tree->right和tree->left代碼）

您是更好地服務於分裂create_node和insert例程分成獨立的功能。這允許create_node被定義爲類型treenode和insert被定義爲類型void。這簡化了每個代碼，並使得邏輯更容易和更易讀。這樣做，你的代碼就變成了：

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

typedef struct treenode 
{ 
char word[20];    //word is the key for each node 
struct treenode *left; 
struct treenode *right; 

} treenode; 

treenode* create_node (char *word) 
{ 
    treenode* tmp = malloc (sizeof (struct treenode)); 
    if (tmp) { 
     strcpy (tmp ->word,word); 
     tmp->left = NULL; 
     tmp->right = NULL; 
    } else { 
     fprintf (stderr, "%s() error: memory exhausted\n", __func__); 
    } 
    return tmp; 
} 

void insert (treenode *tree, char *word) 
{ 

    if (strcmp (word, tree->word) > 0) 
    { 
     if (tree->right == NULL) { 
      tree->right = create_node (word); 
      insert (tree->right, word); 
     } else { 
      insert (tree->right, word); 
     } 
    } 
    else if (strcmp (word, tree->word) < 0) 
    { 
     if (tree->left == NULL) { 
      tree->left = create_node (word); 
      insert (tree->left, word); 
     } else { 
      insert (tree->left, word); 
     } 
    } 
} 

void printinorder(treenode *node) 
{ 
    if(node == NULL) return; 
    printinorder(node-> left); 
    printf("%s ",node-> word); 
    printinorder(node-> right); 
} 

int main() 
{ 
    treenode *root = NULL; 
    char string[20]; 
    scanf ("%s",string); //first input is taken once here and once again inside loop,but its OK 
    root = create_node (string); //duplicate entries are also stored 

    while (strcmp (string,".")!=0) //input is terminated by a full stop 
    { 
     insert (root, string); 
     scanf ("%s",string); 
    } 

    printinorder(root);   //finally printing the BST 

    return 0; 
}

編譯/運行：

$ gcc -Wall -Wextra -o bst bst.c 
$ ./bst 
my_dog 
has 
fleas 
my_cat 
likes 
snakes 
. 
fleas has likes my_cat my_dog snakes

此外，如在評論中提到 - 不要投malloc的。這是不必要的，並增加了錯誤的可能性。

來源

2014-10-11 07:28:40

樹不會超出大小3

回答

相關問題