AVL树中节点删除的奇怪值

Question

制作了一棵 AVL 树，一切都运行良好，直到我用大量插入对其进行了测试。删除具有两个子节点的节点后，“移动”的节点内的数据字段会获得一个奇怪的值。我学到的是 C++ 中一些未定义的行为。我不知道如何去做。我错过了什么？

AVL_Tree.cpp

#include "AVL_Tree.h"
#include "stddef.h"
#include <stdexcept>
#include <iostream>
#include <algorithm>

/*
 * Constructor for TreeNode
 */
AVL_Tree::TreeNode::TreeNode(const int& data)
        : data(data), height(1), leftChild(NULL), rightChild(NULL){};

void AVL_Tree::TreeNode::printNodeValue()
{
    std::cout << data << "\n";
}

void AVL_Tree::TreeNode::printTree(bool isRight, const std::string& indent)
{
    if(rightChild != NULL)
    {
        rightChild->printTree(true, indent + (isRight ? "       " : " |     "));
    }
    std::cout << indent;
    if(isRight)
    {
        std::cout << " /";
    }
    else
    {
        std::cout << " \\";
    }
    std::cout << "----- ";
    printNodeValue();
    if(leftChild != NULL)
    {
        leftChild->printTree(false, indent + (isRight ? " |     " : "       "));
    }
}

void AVL_Tree::TreeNode::printTree()
{
    if(rightChild != NULL)
    {
        rightChild->printTree(true, "");
    }
    printNodeValue();
    if(leftChild != NULL)
    {
        leftChild->printTree(false, "");
    }
}

/*
 * Constructor for the AVL_Tree
 */
AVL_Tree::AVL_Tree()
{
    this->root = NULL;
    this->size = 0;
}

/**
 * Destructor
 */
AVL_Tree::~AVL_Tree()
{
    destruct(this->root);
}

/**
 * Deletes TreeNode objects recursively
 */
void AVL_Tree::destruct(TreeNode* root)
{
    if(root != NULL)
    {
        destruct(root->rightChild);
        destruct(root->leftChild);
        delete root;
        root = NULL;
    }
}

/**
 *Removes specified node
 */
void AVL_Tree::deleteNode(const int& data)
{
    TreeNode* temp = remove(this->root, data);
    if(temp != NULL)
    {
        this->root = temp;
        size--;
    }
}

/**
 *Adds new node to the tree by calling insert()
 */
void AVL_Tree::add(const int& data)
{
    try
    {
        TreeNode* node = new TreeNode(data);
        this->root = insert(this->root, node);
        size++;
    }
    catch(std::string s)
    {
        std::cout << s << std::endl;
    }
}

void AVL_Tree::print()
{
    root->printTree();
}

/**
 * Prints the tree in ascending order
 */
void AVL_Tree::inOrder(TreeNode* current)
{
    if(current != NULL)
    {
        inOrder(current->leftChild);
        std::cout << current->data << std::endl;
        inOrder(current->rightChild);
    }
}

/**
 *Recursively traverse the tree to find the correct place for the new node and then
 *returns the tree.
 */
AVL_Tree::TreeNode* AVL_Tree::insert(TreeNode* current, TreeNode* newNode)
{
    if(current == NULL)
    {
        return newNode;
    }
    if(newNode->data < current->data)
    {
        current->leftChild = insert(current->leftChild, newNode);
    }
    else if(newNode->data > current->data)
    {
        current->rightChild = insert(current->rightChild, newNode);
    }
    else
    {
        throw std::string("Data already exist in tree");
    }
    //return current;
    return balance(current);
}



/**
 * Recursively finds the TreeNode that matches 'dataToRemove' and erase it from the tree then returns the new tree
 */
AVL_Tree::TreeNode* AVL_Tree::remove(TreeNode* current, const int& dataToRemove)
{
    if(current == NULL)
    {
        return current;
    }
    if(dataToRemove < current->data)
    {
        current->leftChild = remove(current->leftChild, dataToRemove);
    }
    else if(dataToRemove > current->data)
    {
        current->rightChild = remove(current->rightChild, dataToRemove);
    }
    else //if(dataToRemove == current->data)
    {
        TreeNode* temp = NULL;
        //No children
        if(current->leftChild == NULL && current->rightChild == NULL)
        {
            delete current;
            current = NULL;
        }
            //One child
        else if(current->leftChild != NULL && current->rightChild == NULL)
        {
            temp = current->leftChild;
            current->data = temp->data;
            current->leftChild = remove(current->leftChild, temp->data);
        }
        else if(current->leftChild == NULL && current->rightChild != NULL)
        {
            temp = current->rightChild;
            current->data = temp->data;
            current->rightChild = remove(current->rightChild, temp->data);
        }
            //Two children
        else if(current->leftChild != NULL && current->rightChild != NULL)
        {
            temp = findSuccessor(current->rightChild);
            current->data = temp->data;
            remove(current->rightChild, temp->data);

        }
    }

    return balance(current);
}

/**
 * Returns height of tree
 */
int AVL_Tree::height(TreeNode* current)
{
    if(current == NULL)
    {
        return 0;
    }
    return current->height;
}

/**
 * Returns the balance factor for the argument(TreeNode pointer)
 */
int AVL_Tree::getBalance(TreeNode* current)
{
    if(current == NULL)
    {
        return 0;
    }
    return height(current->rightChild) - height(current->leftChild);
}

/**
 * Sets the height of the specified TreeNode
 */
void AVL_Tree::fixHeight(TreeNode* current)
{
    int hl = height(current->leftChild);
    int hr = height(current->rightChild);

    current->height = (hl > hr ? hl : hr) + 1;
}

/**
 * Takes TreeNode pointer as arguement and balances the tree if it isn't NULL
 */
AVL_Tree::TreeNode* AVL_Tree::balance(TreeNode* current)
{
    if (current != NULL) {
        fixHeight(current);
        if(getBalance(current) == 2)
        {
            if(getBalance(current->rightChild) < 0)
            {
                current->rightChild = rotateRight(current->rightChild);
            }
            return rotateLeft(current);
        }
        if(getBalance(current) == -2)
        {
            if(getBalance(current->leftChild) > 0)
            {
                current->leftChild = rotateLeft(current->leftChild);
            }
            return rotateRight(current);
        }
        return current;
    } else {
        return NULL;
    }
}

/**
 * Preforms a left rotation
 * Returns the rotated subtree
 */
AVL_Tree::TreeNode* AVL_Tree::rotateLeft(TreeNode* current)
{
    TreeNode* right = current->rightChild;
    current->rightChild = right->leftChild;
    right->leftChild = current;
    fixHeight(current);
    fixHeight(right);
    return right;
}

/**
 * Preforms a right rotation
 */
AVL_Tree::TreeNode* AVL_Tree::rotateRight(TreeNode* current)
{
    TreeNode* left = current->leftChild;
    current->leftChild = left->rightChild;
    left->rightChild = current;
    fixHeight(current);
    fixHeight(left);
    return left;
}

/**
 * Takes TreeNode pointer as argument and return the "leftest"(smallest) node in the right subtree.
 */
AVL_Tree::TreeNode* AVL_Tree::findSuccessor(TreeNode* current)
{

    while(current->leftChild != NULL)
    {
        current = current->leftChild;
    }
    return current;
}

AVL_Tree.h

#ifndef AVLTREE_H
#define AVLTREE_H
#include <string>

class AVL_Tree
{
private:

    struct TreeNode
    {
        TreeNode(const int& data);
        int data;
        int height;
        TreeNode* leftChild;
        TreeNode* rightChild;
        void printTree(bool isRight, const std::string& indent);
        void printTree();
        void printNodeValue();
    };

    int size;
    TreeNode* root;
    TreeNode* findSuccessor(TreeNode* current);
    TreeNode* remove(TreeNode* current, const int& dataToRemove);
    TreeNode* insert(TreeNode* current, TreeNode* newNode);
    int height(TreeNode* current);
    TreeNode* balance(TreeNode* current);
    int getBalance(TreeNode* current);
    TreeNode* rotateLeft(TreeNode* current);
    TreeNode* rotateRight(TreeNode* current);
    void fixHeight(TreeNode* current);
    void destruct(TreeNode* root);
    TreeNode* findMin(TreeNode* current);
    TreeNode* removeMin(TreeNode* current);
public:

    AVL_Tree();
    ~AVL_Tree();
    void deleteNode(const int& data);
    void add(const int& data);
    void print();
    void inOrder(TreeNode* current);
};

#endif

main.cpp

#include "AVL_Tree.h"
#include <stdlib.h>
#include <vector>

using std::vector;

int main()
{
    AVL_Tree at;
    vector<int> list;

    for(int i = 0; i < 20; i++)
    {
        int x = rand() % 100;
        list.push_back(x);
        at.add(x);
    }

    at.print();
    at.add(list[0]);
    at.print();
    for(int i = 19; i >= 18; i--)
    {
        at.deleteNode(list[i]);

    }

    at.print();
    return 0;


}

输出

输出

Answer 1

如果数据已存在于您的树中，您的代码将引发异常。调用代码将指针分配给非返回函数。

this->root = insert(this->root, 节点);

使用一些硬编码值测试您的代码，并确保使用重复值进行测试。