AVL 树代码、数据结构 c++ 中的错误

Question

我真的很想找出我为 AVL 树编写的代码中的错误，但其中似乎存在错误。

它调用了旋转函数，但是当它完成旋转时有几个问题：

root 不变
中序遍历时只显示根值，其他值似乎消失

自 2-3 天以来，我一直在尝试修复此错误，但似乎无法解决。

希望得到你们的帮助。我将附上代码。

/*
insertion
rotations all DONE
level order DONE
deletion
*/
#include <iostream>
#include <queue>
using namespace std;

struct node
{
    int data;
    int height;
    node *left;
    node *right;

    node()
    {
        height = 0;
        left = right = NULL;
    }
};

class AVL
{
public:
    node *root;

    AVL()
    {
        root = NULL;
    }
    // search function
    bool search(int num)
    {
        node *nodePtr = root;

        if (root->data == num)
        {
            cout << "FOUND " << endl;
            return true;
        }

        else
        {
            while (nodePtr != NULL)
            {
                if (nodePtr->data < num)
                {
                    nodePtr = nodePtr->right;
                }

                else if (nodePtr->data > num)
                {
                    nodePtr = nodePtr->left;
                }

                else
                {
                    cout << "FOUND " << endl;
                    return true;
                }
            }
            cout << "NOT FOUND " << endl;
            return false;
        }
    }
    // inorder
    void inorder()
    {
        inorder(root);
    }
    // postorder
    void postorder()
    {
        postorder(root);
    }
    // preorder
    void preorder()
    {
        preorder(root);
    }
    // inorder utility function
    void inorder(node *&nodePtr)
    {
        if (nodePtr)
        {
            inorder(nodePtr->left);
            cout << nodePtr->data << ", ";
            inorder(nodePtr->right);
        }
    }
    // preorder utility function
    void preorder(node *&nodePtr)
    {
        if (nodePtr)
        {
            cout << nodePtr->data << ", ";
            preorder(nodePtr->left);
            preorder(nodePtr->right);
        }
    }
    // postorder utility function
    void postorder(node *&nodePtr)
    {
        if (nodePtr)
        {
            postorder(nodePtr->left);
            postorder(nodePtr->right);
            cout << nodePtr->data << ", ";
        }
    }
    // returns the number of nodes in the tree
    int size(node *&nodePtr)
    {
        if (!nodePtr)
        {
            return 0;
        }

        else
        {
            return  (size(nodePtr->left) + size(nodePtr->right)) + 1;
        }
    }
    // function to check if tree is empty or not
    bool isempty()
    {
        if (root == NULL)
        {
            return true;
        }

        else
        {
            return false;
        }
    }
    // max function to calculate height and also the balance factor
    int maximum(int x, int y)
    {
        if (x>y)
        {
            return x;
        }

        else
        {
            return y;
        }
    }
    // returns the level of the tree
    int returnHeight(node *&nodePtr)
    {
        if (nodePtr == NULL)
        {
            return 0;
        }

        else
        {
            return nodePtr->height;
        }
    }
    // assigning the height to the node
    void assignHeightToNode(node *&nodePtr)
    {
        int left = returnHeight(nodePtr->left);
        int right = returnHeight(nodePtr->right);
        nodePtr->height = maximum(left, right) + 1;
    }
    // single left rotate
    node *singleLeftRotate(node *&nodePtr)
    {
        //      if (nodePtr==NULL)
        //      {
        //          return;
        //      }

        node * b = nodePtr->right;
        nodePtr->right = b->left;
        b->left = nodePtr;
        return b;
    }
    // single right rotate
    node *singleRightRotate(node *&nodePtr)
    {
        //      if (nodePtr==NULL)
        //      {
        //          return ;
        //      }

        node * b = nodePtr->left;
        nodePtr->left = b->right;
        b->right = nodePtr;
        assignHeightToNode(nodePtr);
        assignHeightToNode(b);
        return b;
    }
    // double left rotate
    node *doubleLeft(node *&nodePtr)
    {
        nodePtr->right = singleRightRotate(nodePtr->right);
        return singleLeftRotate(nodePtr);
    }
    // double right rotate
    node *doubleRight(node *&nodePtr)
    {
        nodePtr->left = singleLeftRotate(nodePtr->left);
        return singleRightRotate(nodePtr);
    }
    //   insert function
    void insert1(int x)
    {
        cout << "NOW INSERTING " << x << endl;
        insert2(x, root);
    }
    // insert utility function
    void insert2(int &x, node *&nodePtr)
    {

        if (nodePtr == NULL)
        {
            node *newNode = new node;
            newNode->data = x;
            newNode->height = 0;
            nodePtr = newNode;
            checkRotations(nodePtr, x);
            return;
        }

        else
        {
            if (x < nodePtr->data)
            {
                cout << endl << "GOING LEFT " << endl;
                insert2(x, nodePtr->left);
            }

            else if (x > nodePtr->data)
            {
                cout << endl << "GOING RIGHT " << endl;
                insert2(x, nodePtr->right);
            }

            else if (nodePtr->data == x)
            {
                cout << "DUPLICATE VALUES NOT ALLOWED " << endl;
                return;
            }
        }
        checkRotations(nodePtr, x);
    }
    // checking if rotations needed
    void checkRotations(node *&nodePtr, int &x)
    {
        assignHeightToNode(nodePtr);

        cout << endl << endl << "HEIGHT OF " << nodePtr->data << " IS " << nodePtr->height << endl;
        int bf = returnHeight(nodePtr->left) - returnHeight(nodePtr->right);
        cout << endl << endl << "BALANCE FACTOR AT NODE " << nodePtr->data << " IS " << bf << endl;

        if (bf < -1 || bf > 1)
        {
            cout << endl << endl << "ROTATION IS HAPPEENING " << endl << endl;
            if (x > nodePtr->data)
            {
                singleLeftRotate(nodePtr);
                cout << endl << "ROTATION DONE SINGLE LEFT " << endl;
                return;
            }

            else if (x < nodePtr->data)
            {
                singleRightRotate(nodePtr);
                cout << endl << "ROTATION DONE SINGLE RIGHT " << endl;
                return;
            }

            else if (x < root->data && x > root->left->data)
            {
                doubleRight(nodePtr);
                cout << endl << "ROTATION DONE DOUBLE LEFT " << endl;
                return;
            }

            else if (x > root->data && x < root->right->data)
            {
                doubleLeft(nodePtr);
                cout << endl << "ROTATION DONE DOUBLE LEFT " << endl;
                return;
            }
        }
    }
    // level order display code
    void levelOrderDisplay()
    {
        levelOrderDisplay2(root);
    }
    // level order display utility function
    void levelOrderDisplay2(node *&nodePtr)
    {
        if (nodePtr == NULL)
        {
            cout << "THE TREE IS EMPTY" << endl;
            return;
        }

        queue <node *> displayer;
        displayer.push(nodePtr);

        while (!displayer.empty())
        {
            node *currentNode = displayer.front();
            cout << currentNode->data << ", ";

            if (currentNode->left != NULL)
            {
                displayer.push(currentNode->left);
            }

            else if (currentNode->right != NULL)
            {
                displayer.push(currentNode->right);
            }
            displayer.pop();
        }
    }

    void rootD()
    {
        cout << "root is " << root->data << endl;
    }
};

int main()
{
    AVL tree;
    tree.insert1(3);
    tree.insert1(2);
    tree.insert1(1);

    tree.insert1(4);
    tree.insert1(5);
    tree.insert1(6);
    tree.insert1(7);
    tree.inorder();
    //  tree.rootD();

    //  tree.levelOrderDisplay();
    //  tree.rootD();

    return 0;
}

Answer 1

我建议您不要通过引用传递节点指针，因为您的代码不会更改指针值（例如 print）。试试这个...我在 2 3 天前完成了我的 avl 树代码，我遇到了类似的问题，当我调试我的程序时，我开始知道在打印函数中我的指针值以某种方式发生了变化，因为我通过引用传递了它... .. 所以.. 试试这个，看看是否有效......希望这对你有帮助。

Answer 2

真的很晚回答，但这是你必须做的。您应该将函数中传递的节点设置为等于函数中创建的临时节点。在编码语言中，nodePtr=b 应该是单个旋转函数的最后一行。

希望对您有所帮助:)

AVL 树代码、数据结构 c++ 中的错误

Bug in AVL tree code, data structures c++

c++

data-structures

avl-tree