C++中字符串實現的二叉搜索樹

-1

我已經編寫了一個程序，它將整數值插入到二叉搜索樹中。它似乎工作正常，但當我修改相同的接受字符數組而不是一個整數，我會得到意想不到的結果。這裏是我的完整代碼：C++中字符串實現的二叉搜索樹

struct Node{ 
char data[50]; 
struct Node* right; 
struct Node* left; 
}; 

typedef struct Node* NODE; 

NODE createNode(char data[]){ 
    NODE newNode = (NODE) malloc (sizeof(struct Node)); 

if(!newNode){ 
    cout<<"Not enough memory"<<endl; 
    exit(-1); 
} 
newNode->left = NULL; 
newNode->right = NULL; 
strcpy(newNode->data,data); 
return (newNode); 
} 

void insertNode(NODE* head,char data[]){ 

    NODE newNode = createNode(data); 
    NODE hold_the_head = *head; 
    if(*head == NULL){ 
     *head = newNode; 
     (*head)->right = NULL; 
     (*head)->left = NULL; 
     return; 
    } 

    while(1){ 
     if((newNode->data>(*head)->data)&&((*head)->right==  NULL)){ 
      (*head)->right = newNode; 
      *head = hold_the_head; 
      return; 
     } 
     else if(newNode->data > (*head)->data){ 
      (*head) = (*head)->right; 
     } 

     else if((newNode->data < (*head)->data) && ((*head)->left == NULL)){ 
      (*head)->left = newNode; 
      *head = hold_the_head; 
      return; 
     } 
     else if(newNode->data < (*head)->data){ 
      (*head) = (*head)->left; 
     } 
    } 
} 

void inOrderTraversal(NODE node){ 

    if(node == NULL) 
     return; 
    inOrderTraversal(node->left); 
    cout<<node->data<<"\t"; 
    inOrderTraversal(node->right); 
} 

int main(){ 

    NODE head = NULL; 
    insertNode(&head,"karan"); 
    insertNode(&head,"sameer"); 
    insertNode(&head,"palak"); 
    insertNode(&head,"jagdish"); 
    insertNode(&head,"naman"); 
    insertNode(&head,"umang"); 
    insertNode(&head,"chandu"); 

    inOrderTraversal(head); 
    cout<<endl; 
    return 0; 
}

輸出：

卡蘭薩米爾PALAK賈格迪什·納曼umang chandu

預計：

chandu賈格迪什·卡蘭納曼PALAK薩米爾umang

像這樣的問題已經被問過，但是有一些編譯錯誤。我的代碼沒有拋出任何錯誤，但似乎有一些邏輯缺陷！

來源

2017-01-16 Kenil Patel

除了rachitmanit的回答，我覺得你是用C寫的，而不是C++。

char data[50];

如果您使用C++編寫，我推薦使用std::string。它可以方便地與==，<相比，等

NODE newNode = (NODE) malloc (sizeof(struct Node));

舊的C的malloc只分配內存，並且不構造對象（即不調用構造函數）。它應該是：NODE newNode = new Node;

(*head)->right = NULL; 
(*head)->left = NULL; 
/*etc...*/

NULL通常0是，它是一個整數，而不是指針。我絕對推薦使用nullptr。

void insertNode(NODE* head,char data[]){

通常情況下，指針參數可能是nullptr，你應該檢查是否是。我建議使用的參考，在這裏你不必：void insertNode(NODE &head, std::string data){

cout<<endl;

應該是std::cout<<std::endl。

並且不要忘記釋放內存。你的程序分配內存並不會釋放它，這會導致內存泄漏。 struct Node應該在銷燬時釋放內存：

struct Node { 
    std::string data; 
    Node *right; 
    Node *left; 
    ~Node() { 
     delete right; 
     delete left; 
    } 
}; 
/* ... */ 
int main() { 
    /* ... */ 
    delete head; 
    return 0; 
}

來源

2017-01-16 07:29:41

Thanx很多.. !!其實我曾嘗試使用字符串，而不是字符數組..但是有一個分段錯誤，我無法解決它，所以我決定使用字符數組！ –

同樣，'malloc'不會調用任何構造函數，所以也不會調用成員std :: string的構造函數。可能這就是你得到分段錯誤的原因。 –

這是我不知道的！非常感謝！ –

如果是整數，你的「數據」實際上是一個值。雖然這裏「node-> data」是第一個數據塊[]數組的地址。記住node-> data [0]是一個值。你在這裏比較的地址不是實際的「價值」。

而且，你必須遵循這樣的：How to compare string in an character array?

這應該幫助。

來源

2017-01-16 06:24:36 rachitmanit

明白了！非常感謝你。 –

C++中字符串實現的二叉搜索樹

回答

相關問題