c++ - 二叉搜索树插入垃圾数据

Question

所以，我正在为一个项目编写一个自平衡二叉搜索树，我似乎在插入函数方面遇到了问题。具体来说，这段代码在这里:

if(element > n->data)
{
    n->rightChild = insert(n->rightChild, element);
}   

出于测试目的，我只使用 insert(root, 10) insert(root, 20) insert(root, 30) 等等。问题发生在 insert 30 处。它通过并尝试用另一个非空子树替换一个非空子树 (20)。我不确定为什么我似乎遇到了这个问题，因为递归是我看到这个实现的唯一方法，并且在我发现的所有其他类似问题中，答案都以类似的方式编码对此或与此完全相同。谁能帮我弄清楚发生了什么事？目前，在它尝试用 30 覆盖 20 子树后，它最终用垃圾数据填充根右子树，然后，当它尝试重新平衡时，抛出 EXC_BAD_ACCESS 错误，大概是因为我试图访问一个节点'存在。

源代码

#include <iostream>
using namespace std;

struct node
{
public:
    int data, height;
    node *leftChild, *rightChild;
};
int findMin(struct node *p) // finds the smallest node in the tree
{
    while (p->leftChild != NULL)
        p = p->leftChild;
    return p->data;
}
int findMax(struct node *p) // finds the largest node in the tree
{
    while(p->rightChild != NULL)
        p = p->rightChild;
    return p->data;
}
int max(int a, int b) // gets the max of two integers
{
    if(a > b)
        return a;
    else
        return b;
}
int height(struct node *p) // gets the height of the tree
{
    int lHeight, rHeight;
    if(p == NULL)
        return -1;
    else
    {
        lHeight = height(p->leftChild);
        rHeight = height(p->rightChild);

        if(lHeight > rHeight)
            return lHeight + 1;
        else
            return rHeight + 1;
    }
}
struct node* newNode(int element) // helper function to return a new node with empty subtrees
{
    node* newPtr = (struct node*) malloc(sizeof(newPtr));
    newPtr->data = element;
    newPtr->leftChild = NULL;
    newPtr->rightChild = NULL;
    newPtr->height = 1;
    return newPtr;
}
struct node* rightRotate(struct node* p) // function to right rotate a tree rooted at p
{
    node* child = p->leftChild;
    node* grandChild = child->rightChild;

    // perform the rotation
    child->rightChild = p;
    p->leftChild = grandChild;

    // update the height for the nodes
    p->height = max(height(p->leftChild), height(p->rightChild)) + 1;
    child->height = max(height(child->leftChild), height(child->rightChild)) + 1;

    // return new root
    return child;
}
struct node* leftRotate(struct node* p) // function to left rotate a tree rooted at p
{
    node* child = p->rightChild;
    node* grandChild = child->leftChild;

    // perform the rotation
    child->leftChild = p;
    p->rightChild = grandChild;

    // update heights
    p->height = max(height(p->leftChild), height(p->rightChild)) + 1;

    // return new root
    return child;
}

int getBalance(struct node *p)
{
    if(p == NULL)
        return 0;
    else
        return height(p->leftChild) - height(p->rightChild);
}
// recursive version of BST insert to insert the element in a sub tree rooted with root
// which returns new root of subtree
struct node* insert(struct node*& n, int element)
{
    // perform the normal BST insertion
    if(n == NULL) // if the tree is empty
        return(newNode(element));
    if(element< n->data)
    {
        n->leftChild = insert(n->leftChild, element);
    }
    if(element > n->data)
    {
        n->rightChild = insert(n->rightChild, element);
    }
    else // duplicate node
    {
        return n;
    }

    // update the height for this node
    n->height = 1 + max(height(n->leftChild), height(n->rightChild));

    // get the balance factor to see if the tree is unbalanced
    int balance = getBalance(n);

    // the tree is unbalanced, there are 4 different types of rotation to make
    // Single Right Rotation (Left Left Case)
    if(balance > 1 && element < n->leftChild->data)
    {
        return rightRotate(n);
    }
    // Single Left Rotation (Right Right Case)
    if(balance < -1 && element > n->rightChild->data)
    {
        return leftRotate(n);
    }
    // Left Right Rotation
    if(balance > 1 && element > n->leftChild->data)
    {
        n->leftChild = leftRotate(n->leftChild);
        return rightRotate(n);
    }
    // Right Left Rotation
    if(balance < -1 && element < n->rightChild->data)
    {
        n->rightChild = rightRotate(n->rightChild);
        return leftRotate(n);
    }
    cout << "Height: " << n->height << endl;
    // return the unmodified root pointer in the case that the tree does not become unbalanced
    return n;
}
void inorder(struct node *p)
{
    if(p != NULL)
    {
        inorder(p->leftChild);
        cout << p->data << ", ";
        inorder(p->rightChild);
    }
}
void preorder(struct node *p)
{
    if(p != NULL)
    {
        cout << p->data << ", ";
        preorder(p->leftChild);
        preorder(p->rightChild);
    }
}
void print(struct node* root)
{
    cout << "Min Value: " << findMin(root) << endl;
    cout << "Max Value: " << findMax(root) << endl;
    cout << "Pre Order: ";
    preorder(root);
    cout << "Inorder: ";
    inorder(root);
}

int main()
{
    struct node* root = NULL;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

//    int array[11] = {25, 5, 6, 17, 34, 2, 57, 89, 12, 12, 73};
//    for(int i = 0; i < 11; i++)
//    {
//        root = insert(root, array[i]);
//    }

    preorder(root);
    return 0;
}

Answer 1

我不确定这是你遇到的唯一问题，但它是一个可能导致严重故障的问题:

struct node* newNode(int element) // helper function to return a new node with empty subtrees
{
    node* newPtr = (struct node*) malloc(sizeof(newPtr));

在这里你分配内存来保存一个node*。

您需要的是保存节点的内存。

试试这个:

struct node* newNode(int element) // helper function to return a new node with empty subtrees
{
    node* newPtr = (struct node*) malloc(sizeof(*newPtr));
                                                ^
                                              notice

更新:

在评论中 OP 要求:

That actually did fix it, thank you! Could someone explain why though?

当你这样做的时候:

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

这与:

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

所以你分配了内存来保存一个指针 - 这可能是 8 或 4 个字节。

然后你开始用这段代码写入内存区域:

newPtr->data = element;
newPtr->leftChild = NULL;
newPtr->rightChild = NULL;
newPtr->height = 1;

这些写入占用了超过分配的 8(或 4)个字节，因此您写入不属于您的程序的内存。这是未定义的行为(又名“任何事情都可能发生”)，从那里分析出了什么问题是没有意义的。

但是，内存很可能稍后被覆盖(例如，在第二个 malloc 之后)，从而破坏了最初写入的值。因此，当您再次读取内存时，您会得到一些与最初写入的值不同的东西，从那里开始，一切都出错了。