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;