-1

我正在为我的数据结构类创建一个使用二叉搜索树的优先级队列。但是当我尝试输出队列时，我总是得到 0。我查看了我的 DeleteLargest 和 Dequeue 成员函数，但我找不到错误

测试.cpp

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

int main()
{

    int num, input, output;
    cout << "Enter number of elements: ";
    cin >> num;
    PriorityQueueBST p;
    for (int x = 0; x < num; x++)
    {
        cout << "Enter number " << x + 1  
            << " of " << num << ": ";
        cin >> input;
        p.Enqueue(input);
    }
    for (int y = 0; y < num; y++)
    {
        cout << "Outputting number " << y + 1  
            << " of " << num << ": ";
        if(p.IsEmpty())
        {
            break; //we are done (this is an error!)
        }
        output = p.Dequeue();
        cout << output << endl;
    }

    system("pause");
    return 0;
    //CTree* tr = new CTree();
    //
    //for (int i = 0; i < 3; i++)
    //  tr->Add();

    //tr->View();
    //system("pause");


    //return 0;
}

BST 声明文件

//#ifndef CTREE_H
//#define CTREE_H
//using namespace std;

struct TreeNode
{
    int info;
    TreeNode* leftLink;
    TreeNode* rightLink;
};


class CTree
{

private:


    void AddItem( TreeNode*&, TreeNode*);
    void DisplayTree(TreeNode*);
    void Retrieve(TreeNode*&, TreeNode*,bool&);
    void Destroy(TreeNode*&);

public:
    CTree();
    ~CTree();
    void Add();
    void View();
    bool IsEmpty();
    int DeleteLargest(TreeNode*&);
    TreeNode *tree;
};


//#endif

BST 实施文件

#include <iostream>
#include <string>

using namespace std;

#include "CTree.h"

CTree::CTree()
{
    tree = NULL;
}

CTree::~CTree()
{
    Destroy(tree);
}

void CTree::Destroy(TreeNode*& tree)
{
    if (tree != NULL)
    {
    Destroy(tree->leftLink);
    Destroy(tree->rightLink);
    delete tree;
    }
}


bool CTree::IsEmpty()
{
    if(tree == NULL) 
    {
        return true;
    }
    else
    {
        return false;
    }
}

void CTree::Add()
{
    TreeNode* newPerson = new TreeNode();
    /*cout << "Enter the person's name: ";
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
    cin.getline(newPerson->name, 20);*/
   /* cout << "Enter the person's contribution: ";
    cin >> newPerson->info;*/
    /*bool found = false;*/


    newPerson->leftLink = NULL;
    newPerson->rightLink = NULL;

    /*Retrieve(tree, newPerson, found);
     if (found)
         cout << "info allready entered\n";
     else*/
         AddItem(tree, newPerson);
}

void CTree::View()
{
    if (IsEmpty())
    {
        cout<<"The list is empy";
    }
    else
    {
        DisplayTree(tree);

    }

};

void CTree::AddItem( TreeNode*& ptr, TreeNode* newPer )
{
        if (ptr == NULL)
        {
            ptr = newPer;
        }
        else if ( newPer->info < ptr->info)
            AddItem(ptr->leftLink, newPer); 
        else
            AddItem(ptr->rightLink, newPer); 
}
void CTree::DisplayTree(TreeNode* ptr)
{
    if (ptr == NULL)
                    return;
    DisplayTree(ptr->rightLink);
    cout << ptr->info << endl; //cout<<ptr->name<<" "<<"$"<<ptr->info <<endl;
    DisplayTree(ptr->leftLink); 
}
void CTree::Retrieve(TreeNode*& ptr, TreeNode* newPer, bool& found)
{
    {
        if (ptr == NULL)
        {
            found = false; // item is not found.
        }
        else if ( newPer->info < ptr->info)
        {
            Retrieve(ptr->leftLink, newPer, found);
        }
             // Search left subtree.
        else if (newPer->info > ptr->info)
        {
            Retrieve(ptr->rightLink, newPer, found);// Search right subtree.
        }   
        else
        {
            //newPer.info = ptr->info; // item is found.
            found = true;
        }
    }
}

int CTree::DeleteLargest(TreeNode*& tr)
{
    int largest = 0;;
    TreeNode* prev;
    TreeNode* cur;
    prev = NULL;
    cur = tr;

    if (tr == NULL)
    {
        cout <<  "The tree is empty"<<endl;
    }
    else if (tr->rightLink == NULL)
    {
        largest = tr->info;
    }
    else
    {
        prev = tr;
        tr = tr->rightLink;
        DeleteLargest(tr);
    }

    return largest;
}

优先队列声明

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

#ifndef PRIORITYQUEUESLL__H
#define PRIORITYQUEUESLL__H

class PriorityQueueBST
{
    public:
        PriorityQueueBST();
        ~PriorityQueueBST();
        void Enqueue(int);
        int Dequeue();
        bool IsEmpty();

    private:
        CTree* ourTree;
        //sslNode* head;
};

#endif

优先队列实现

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

PriorityQueueBST::PriorityQueueBST()
{
    ourTree = new CTree();
    //head = NULL;
}

PriorityQueueBST::~PriorityQueueBST()
{

}

void PriorityQueueBST::Enqueue(int dataToEnter)
{
    ourTree->Add();
}

int PriorityQueueBST::Dequeue()
{
    //check for empty??
    return ourTree->DeleteLargest(ourTree->tree);
}

bool PriorityQueueBST::IsEmpty()
{
    return ourTree->IsEmpty();

}
4

1 回答 1

1

您的输出始终为 0，因为在

int CTree::DeleteLargest(TreeNode*& tr)
{
    int largest = 0;;
    TreeNode* prev;
    TreeNode* cur;
    prev = NULL;
    cur = tr;

    if (tr == NULL)
    {
        cout <<  "The tree is empty"<<endl;
    }
    else if (tr->rightLink == NULL)
    {
        largest = tr->info;
    }
    else
    {
        prev = tr;
        tr = tr->rightLink;
        DeleteLargest(tr);
    }

    return largest;
}

如果is ，您只会设置largest一些潜在的东西。否则，您会重复并将变量本地设置为函数的另一个调用。当递归再次上升时，该更改将丢失，并且在最顶层的调用中，仍为 0。!= 0tr->rightlinkNULLlargestlargest

在else分支的最后一行，您应该

largest = DeleteLargest(tr);

或者

return DeleteLargest(tr);

Another problem is that, despite its name, deleteLargest doesn't actually delete anything, so with the above, you would still always get the same value.

于 2012-09-14T19:00:49.200 回答