C++ BST arbre insérer une chaîne

Question

J'essaye de créer un BST dont les données sont une chaîne .. cependant, il ne semble pas aimer la valeur de chaîne .. si je change le type de données en int, le code fonctionne. Je ne sais pas pourquoi.peut-on aider quelqu'un? ici est le code

// BST.cpp : Defines the entry point for the console application. 
// 

#include "stdafx.h" 
#include<stdio.h> 
#include<stdlib.h> 
#include<string> 
#include<iostream> 

using namespace std; 

// An AVL tree node 
struct Node 
{ 
    string key; 
    struct Node *left; 
    struct Node *right; 
    int height; 
    int counter; 
}; 

// A utility function to get maximum of two integers 
int max(int a, int b); 

// A utility function to get height of the tree 
int height(struct Node *N) 
{ 
    if (N == NULL) 
     return 0; 
    return N->height; 
} 

// A utility function to get maximum of two integers 
int max(int a, int b) 
{ 
    return (a > b) ? a : b; 
} 

/* Helper function that allocates a new node with the given key and 
NULL left and right pointers. */ 
struct Node* newNode(const string& key) 
{ 
    struct Node* node = (struct Node*) 
     malloc(sizeof(struct Node)); 
    node->key = key; 
    node->left = nullptr; 
    node->right = nullptr; 
    node->counter = 0; 
    node->height = 1; // new node is initially added at leaf 
    return(node); 
} 

// A utility function to right rotate subtree rooted with y 
// See the diagram given above. 
struct Node *rightRotate(struct Node *y) 
{ 
    struct Node *x = y->left; 
    struct Node *T2 = x->right; 

    // Perform rotation 
    x->right = y; 
    y->left = T2; 

    // Update heights 
    y->height = max(height(y->left), height(y->right)) + 1; 
    x->height = max(height(x->left), height(x->right)) + 1; 

    // Return new root 
    return x; 
} 

// A utility function to left rotate subtree rooted with x 
// See the diagram given above. 
struct Node *leftRotate(struct Node *x) 
{ 
    struct Node *y = x->right; 
    struct Node *T2 = y->left; 

    // Perform rotation 
    y->left = x; 
    x->right = T2; 

    // Update heights 
    x->height = max(height(x->left), height(x->right)) + 1; 
    y->height = max(height(y->left), height(y->right)) + 1; 

    // Return new root 
    return y; 
} 

// Get Balance factor of node N 
int getBalance(struct Node *N) 
{ 
    if (N == NULL) 
     return 0; 
    return height(N->left) - height(N->right); 
} 

// Recursive function to insert key in subtree rooted 
// with node and returns new root of subtree. 
struct Node* insert(struct Node* node, string key) 


{ 
    /* 1. Perform the normal BST insertion */ 
    if (node == NULL) 
     return(newNode(key)); 

    if (key < node->key) 
     node->left = insert(node->left, key); 
    else if (key > node->key) 
     node->right = insert(node->right, key); 
    else // Equal keys are not allowed in BST 
    { 
     node->counter++; 
     return node; 
    } 
    /* 2. Update height of this ancestor node */ 
    node->height = 1 + max(height(node->left), 
     height(node->right)); 

    /* 3. Get the balance factor of this ancestor 
    node to check whether this node became 
    unbalanced */ 
    int balance = getBalance(node); 

    // If this node becomes unbalanced, then 
    // there are 4 cases 

    // Left Left Case 
    if (balance > 1 && key < node->left->key) 
     return rightRotate(node); 

    // Right Right Case 
    if (balance < -1 && key > node->right->key) 
     return leftRotate(node); 

    // Left Right Case 
    if (balance > 1 && key > node->left->key) 
    { 
     node->left = leftRotate(node->left); 
     return rightRotate(node); 
    } 

    // Right Left Case 
    if (balance < -1 && key < node->right->key) 
    { 
     node->right = rightRotate(node->right); 
     return leftRotate(node); 
    } 

    /* return the (unchanged) node pointer */ 
    return node; 
} 

// A utility function to print preorder traversal 
// of the tree. 
// The function also prints height of every node 
void preOrder(struct Node *root) 
{ 
    if (root) 
    { 
     cout << root->key << endl;; 
     preOrder(root->left); 
     preOrder(root->right); 
    } 
} 

/* Drier program to test above function*/ 
int main() 
{ 
    struct Node *root = nullptr; 

    /* Constructing tree given in the above figure */ 

    root = insert(root, "a"); 
    root = insert(root, "bc"); 
    root = insert(root, "DE"); 
    root = insert(root, "op"); 
    root = insert(root, "lo"); 
    root = insert(root, "mp"); 

    /*root = insert(root, 10); 
    root = insert(root, 20); 
    root = insert(root, 30); 
    root = insert(root, 40); 
    root = insert(root, 50); 
    root = insert(root, 25);*/ 

    printf("Preorder traversal of the constructed AVL" 
     " tree is \n"); 
    preOrder(root); 

    return 0; 
} 

Answer 1

Une question est ici:

struct Node* node = (struct Node*)malloc(sizeof(struct Node));

Cela ne fonctionnera pas correctement. La classe Node a std::string en tant que membre et l'utilisation de malloc pour créer des instances dynamiques n'appelle pas le constructeur pour std::string. La fonction malloc ne sait rien sur C++ constructeurs ou objets.

En C++, il y a quelque chose appelé POD Type (Plaine-Vieux-Data), qui est essentiellement un type compatible C. L'appel malloc ne fonctionnera correctement que pour les types POD. Lorsque vous avez modifié le membre Node de int à std::string, vous avez modifié Node d'un type POD à un type non POD. Une fois que votre type est non-POD, des fonctions telles que malloc pour créer des instances ne fonctionneront pas comme prévu.

L'appel malloc alloue juste la mémoire, et rien d'autre. Il ne sait pas comment appeler le constructeur pour les classes C++ (telles que std::string), donc votre objet Node a un std::string non construit non validé. L'utiliser provoque un comportement indéfini.

Pour remédier à cela, utilisez new, pas malloc pour créer des instances dynamiques de Node, depuis new appelle le constructeur pour le type non-POD.

Node* node = new Node();

Même si Node étaient POD, vous devez utiliser new au lieu de malloc.

---

Vous n'avez pas non plus besoin de spécifier struct partout. En utilisant struct comme c'est un report de C, et n'est pas nécessaire pour C++.

Exemple: Au lieu de ceci:

struct Node *rightRotate(struct Node *y) 
{ 
    struct Node *x = y->left; 
    struct Node *T2 = x->right; 

c'est tout ce que vous avez besoin pour C++:

Node *rightRotate(Node *y) 
{ 
    Node *x = y->left; 
    Node *T2 = x->right;