C++ BSTツリーは文字列を挿入します

Question

データが文字列であるBSTを作成しようとしていますが、文字列値が好きではないようです。データ型をintに変更するとコードが動作します。私はなぜ...誰かを助けることができないのですか？ は、ここにコード

// 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

1つの問題はここです：

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

これは正しく動作しません。 Nodeクラスはメンバーとしてstd::stringを持ち、mallocを使用して動的インスタンスを作成すると、std::stringのコンストラクターは呼び出されません。 malloc関数は、C++コンストラクタまたはオブジェクトについて何も知らない。

はC++では、基本的にC互換性のある型であるPOD（プレインオールド・データ）タイプと呼ばれるもの、があります。 mallocコールはPODタイプに対してのみ正しく動作します。 Nodeメンバーをintからstd::stringに変更した場合は、NodeをPODタイプから非PODタイプに変更しました。あなたのタイプがPODでなければ、インスタンスを作成するためのmallocなどの関数は期待どおりに機能しません。

mallocコールではメモリだけが割り当てられます。 C++クラスのコンストラクタ（たとえばstd::string）を呼び出す方法がわからないため、Nodeオブジェクトは無効で、構造化されていないstd::stringオブジェクトを持っています。それを使用すると、未定義の動作が発生します。

newが非PODタイプのコンストラクタを呼び出しているので、Nodeの動的なインスタンスを作成するnew、ないmallocを使用し、これを軽減するには。

Node* node = new Node();

NodeはPODあったとしても、あなたの代わりにmallocのnewを使用する必要があります。

---

どこでもstructを指定する必要はありません。そのようなstructを使用すると、Cからのホールドオーバーであり、C++では必要ありません。

例：この代わりに：

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

これはあなたがC++のために必要なすべてのです：

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