0

我正在用 C++ 编写一个 AVL 树程序。我基于我之前制作的 BST 优先队列程序。不幸的是，每次添加应该导致旋转的新节点时，都会引发堆栈溢出异常。

到目前为止，这是我的代码：

节点.h

#ifndef NODE_H_
#define NODE_H_

#include "stdio.h"
#include <iostream>
using namespace std;

class node
{
    public:node(int inputValue)
        {
            value = inputValue;
            Right = NULL;
            Left = NULL;
            Parent = NULL;
        }

        node* Right;
        node* Left;
        node* Parent;
        int value;
        int Priority;

        int AvlValue;
        void UpdateHeight();

    private:int Height(node* root);
};

void node::UpdateHeight()
{
    int Right = Height(this->Right);
    int Left = Height(this->Left);
    if (Right == -1)
        Right = 0;
    if (Left == -1)
        Left = 0;

    AvlValue = Left - Right;
}

int node::Height(node* root)
{
    if (root == NULL) return -1;
    return max(Height(root->Left), Height(root->Right)) + 1;
}
#endif

AVL.h

#ifndef AVL_H_
#define AVL_H_

#include "node.h"
#include <string>
#include <iostream>
using namespace std;

class AVL
{
    private:
        int size;
        node* head;
    public:
        AVL(void);
        ~AVL(void);

        void ADD(int nvalue, int nPriority);
        int Peek();
        int RemoveAndDisplay();
        int Height(node* root);
        int SearchFor(int Priority);

        void MenuSelection(int indicator);
        void Controller();
        int MainMenu();

        void PreOrder(node* root);
        void inorder(node* root);

        void Traverse(node* root);
        node* First();
        void LevelOut();

        node* LRotation(node* current);
        node* RRotation(node* current);
        node* DoubleRotationLR(node* current);
        node* DoubleRotationRL(node* current);
};

AVL::AVL()
{
    size = 0;
    head = NULL;
}

AVL::~AVL()
{
}

void AVL::LevelOut()
{
    Traverse(head);

    node* sort;
    node* current = head;
    while(current->Left != NULL || current->Right != NULL)
    {
        if(current->AvlValue != 2 && current->AvlValue != -2)
        {
            if(current->Left != NULL)
            {
                current = current->Left;
            }
            else if(current->Right != NULL)
            {
                current = current->Right;
            }
        }
        else
        {
            sort = current;
            if (sort->AvlValue == 2)
            {
                if (sort->Left->AvlValue == 1)
                {
                    RRotation(sort);
                    Traverse(head);
                }
                else if(sort->Left->AvlValue == -1)
                {
                    DoubleRotationLR(sort);
                    Traverse(head);
                }
            }
            else
            {
                if (sort->Right->AvlValue == -1)
                {
                    LRotation(sort);
                    Traverse(head);
                }
                else if(sort->Right->AvlValue == 1)
                {
                    DoubleRotationRL(sort); 
                    Traverse(head);
                }
            }
        }
    }
}

node* AVL::LRotation(node* current)
{
    node* RightChild = current->Right;
    current->Parent = RightChild;
    RightChild->Left = current;

    return RightChild;
}

node* AVL::RRotation(node* current)
{
    node* LeftChild = current->Left;
    current->Parent = LeftChild;
    LeftChild->Right = current;

    return LeftChild;
}

node* AVL::DoubleRotationLR(node* current)
{
    node* tmp = current;
    tmp->Left = LRotation(tmp->Left);
    tmp = RRotation(tmp);
    return tmp;
}

node* AVL::DoubleRotationRL(node* current)
{
    node* tmp = current;
    tmp->Right = RRotation(tmp->Right);
    tmp = LRotation(tmp);
    return tmp;
}

int AVL::Peek()
{
    node* current = head;
    while(current->Left != NULL)
    {
        current = current->Left;
    }
    return current->value;
}

int AVL::RemoveAndDisplay()
{
    int valueReturn = -1;
    node* current = head;
    node* deleterPointer;

    if(current->Left != NULL)
    {
        while(current->Left != NULL)
        {
            current = current->Left;
        }
        valueReturn = current->value;

        deleterPointer = current->Parent;
        delete current;
        deleterPointer->Left = NULL;
    }
    else
    {
        valueReturn = current->value;
        current = current->Right;
        delete head;
        head = current;
    }
    size--;
    LevelOut();
    return valueReturn;
}

int AVL::SearchFor(int sPriority)
{
    node* current = head;
    bool keepGoing = true;
    int valueToReturn = -1;

    while(keepGoing)
    {
        if(current->Priority == sPriority)
        {
            valueToReturn = current->value;
            keepGoing = false;
        }
        else
        {
            if(current->Priority > sPriority && current->Left != NULL)
            {
                current = current->Left;
                keepGoing = true;
            }
            else if(current->Priority < sPriority && current->Right != NULL)
            {
                current = current->Right;
                keepGoing = true;
            }
            else
            {
                keepGoing = false;
            }
        }
    }
    return valueToReturn;
}

void AVL::ADD(int nvalue, int nPriority)
{
    node* current = head;
    bool nextLvL = true;
    if (head == NULL)
    {
        head = new node(nvalue);
        head->Priority = nPriority;
    }
    else
    {
        while(nextLvL)
        {
            if(current->Priority > nPriority)
            {
                if(current->Left != NULL)
                {
                    current = current->Left;
                    nextLvL = true;
                }
                else
                {
                    current->Left = new node(nvalue);
                    current->Left->Priority = nPriority;
                    current->Left->Parent = current;
                    nextLvL = false;
                }
            }
            else
            {
                if (current->Right != NULL)
                {
                    current = current->Right;
                    nextLvL = true;
                }
                else
                {
                    current->Right = new node(nvalue);
                    current->Right->Priority = nPriority;
                    current->Right->Parent = current;
                    nextLvL = false;
                }
            }
        }
    }
    size++;
    LevelOut();
}

int AVL::MainMenu()
{
    int inputvalue = 0;
    cout << "\t Main Menu " << endl;
    cout << "   1. Add " << endl;
    cout << "   2. Remove " << endl;
    cout << "   3. Peek " << endl;
    cout << "   4. SearchFor " << endl;
    cout << "   5. Size " << endl;
    cout << "   6. Inorder " << endl;
    cout << "   7. PreOrder " << endl;
    cout << "   8. Height " << endl;
    cout << "   0. Quit " << endl;

    cout << "  Input: ";
    cin>>inputvalue;
    return inputvalue;
}

void AVL::MenuSelection(int indicator)
{
    int userInput = -1;
    int prior;
    int SearchForValue = -1;

    switch(indicator)
    {
    case 1:
        cout << "Value to add: ";
        cin>> userInput;
        cout << "Priority for input: ";
        cin>> prior;
        ADD(userInput, prior);
        break;
    case 2:
        cout << "Item Removed: " << RemoveAndDisplay() << endl;
        break;
    case 3:
        cout << "The first item in the Queue has a value of: " << Peek() << endl;
        break;
    case 4:
        cout << "Priority to Search for: ";
        cin>> prior;
        SearchForValue = SearchFor(prior);
        break;
    case 5:
        cout << "Total items in the Queue is: " << size << endl;
        break;
    case 6:
        cout << "First Value: " << First()->value << endl;
        inorder(head);
        printf("\n");
        break;
    case 7:
        PreOrder(head);
        printf("\n");
        break;
    case 8:
        cout << Height(head) << endl;
        break;
    case 0:
        cout << "\tGood Bye!" << endl;
        break;
    default:
        break;
    }

}

node* AVL::First()
{
    node* current = head;
    while(current->Left != NULL)
        current = current->Left;
    return current;
}

void AVL::Traverse(node* root)
{
    if (root != NULL)
    {
        root->UpdateHeight();
        Traverse(root->Left);
        Traverse(root->Right);
    }
}

void AVL::PreOrder(node* root)
{
    if(root != NULL){
        cout << root->value << ", ";
        PreOrder(root->Left);
        PreOrder(root->Right);
    }
}

void AVL::inorder(node* root)
{
    if(root != NULL){
        inorder(root->Left);
        cout << root->value << ", ";
        inorder(root->Right);
    }
}

int AVL::Height(node* root)
{
    if (root == NULL) return -1;
    return max(Height(root->Left), Height(root->Right)) + 1;
}

void AVL::Controller()
{
    int input = -1;
    while(input != 0)
    {
        input = MainMenu();
        MenuSelection(input);
    }
}

#endif

AVL.cpp

#include "AVL.h"


int main()
{
    AVL avl;
    avl.Controller();
    return 0;
}
4

2 回答 2

0

似乎是一个逻辑错误 - 经过一些printf调试后，有时一个被称为的节点似乎root->Left仍将root作为其Right成员。因此，呼叫Height(root->Left)最终将尝试Height(root->Left->Right)并再次遇到root。

（另外，Height()应该声明为静态的，因为它不this以任何方式使用。）

于 2012-05-18T05:16:20.920 回答
0

您真的要忽略 Rotation 调用的函数的返回值LevelOut吗？

例如，AVL::LevelOut调用： RRotation(sort)

其中宣布： node* AVL::RRotation(node* current)

:-)

于 2012-05-18T05:27:39.633 回答