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

的一个问题是在这里：

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

这将无法正常工作。 Node类具有std::string作为成员，并且使用malloc创建动态实例不会调用std::string的构造函数。 malloc函数对构造函数或对象不了解。

在C++，有一种叫做POD（中的旧式数据）型，基本上是一个C兼容型。 malloc呼叫仅适用于POD类型。当您将Node成员从int更改为std::string时，您将Node从POD类型更改为非POD类型。一旦您的类型为非POD，则创建实例的功能（例如malloc）将无法按预期工作。

malloc调用只是分配内存，没有别的。它不知道如何调用C++类的构造函数（例如std::string），因此您的Node对象具有无效的未构造函数std::string。使用它会导致未定义的行为发生。

为了缓解这一点，使用new而不是malloc来创建动态实例Node，因为new调用非POD类型的构造函数。

Node* node = new Node();

即使Node是POD，你应该使用new而不是malloc。

---

您也不需要在任何地方指定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;