2

我为我的数据结构类编写了一个使用二叉搜索树的优先级队列。它产生的输出对于某些输入是正确的，而对于其他输入则不正确。 正确的输出：

输入元素数量：5

输入第 1 个，共 5 个：1

输入第 2 个，共 5 个：2

输入第 3 个，共 5 个：3

输入第 4 个，共 5 个：4

输入第 5 个，共 5 个：5

输出 5 个中的第 1 个：5

输出 5 个中的第 2 个：4

输出 5 个中的第 3 个：3

输出 5 个中的第 4 个：2

输出 5 个中的第 5 个：1

按任意键继续 。. .

输出不正确

输入元素数量：5

输入第 1 个，共 5 个：-56

输入第 2 个，共 5 个：4

输入第 3 个，共 5 个：56

输入第 4 个，共 5 个：21

输入第 5 个，共 5 个：32

输出 5 个中的第 1 个：56

输出 5 个中的第 2 个：4

输出 5 个中的第 3 个：-56

输出 5 个中的第 4 个：-56

输出 5 个中的第 5 个：-56

按任意键继续 。. .

测试.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
{
public:
    CTree();
    ~CTree();
    void Add(int);
    void View();
    bool IsEmpty();
    int DeleteLargest(TreeNode*);
    TreeNode *tree;
private:    
    void AddItem( TreeNode*&, TreeNode*);
    void DisplayTree(TreeNode*);
    void Retrieve(TreeNode*&, TreeNode*,bool&);
    void Destroy(TreeNode*&);
};


//#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(int dataToEnter)
{
    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->info = dataToEnter;
    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 = tr->info;
    TreeNode* prev = NULL;

    while (tr->rightLink != NULL)
    {
        prev = tr;
        tr = tr->rightLink;
        largest = tr->info;
    }

    if (prev != NULL && prev->rightLink != NULL)
    {
        delete prev->rightLink;
        prev->rightLink = NULL;
    }

    return largest;
}
//
//int CTree::DeleteLargest(TreeNode* tr)
//{
//  int largest = 0;
//  TreeNode* prev = NULL;
//
//  
//  while (tr->rightLink != NULL)
//  {
//      prev = tr;
//      tr = tr->rightLink;
//      largest = tr->info;
//  }
//
//  prev->rightLink = NULL;
//      
//  return largest;
//}

/*


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

    */

PQ 声明

//#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

PQ 实施

#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(dataToEnter);
}

int PriorityQueueBST::Dequeue()
{

    //check for empty??
    return ourTree->DeleteLargest(ourTree->tree);
}

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

}
4

1 回答 1

3

在DeleteLargest中，考虑如果树看起来像

        4
       / \
      /   \
     2     7
    / \   /
    1  3  5

和

int CTree::DeleteLargest(TreeNode* tr)
{
    int largest = tr->info;
    TreeNode* prev = NULL;

    while (tr->rightLink != NULL)
    {
        prev = tr;
        tr = tr->rightLink;
        largest = tr->info;
    }

    if (prev != NULL && prev->rightLink != NULL)
    {
        delete prev->rightLink;
        prev->rightLink = NULL;
    }

    return largest;
}

你找到了 7，但是把 5 从树上剪下来，然后它就丢失了。而当根节点的右子树已经被完全删除后，tr->rightLink从头NULL开始，所以prev仍然存在NULL，什么都没有被删除。

对于第一种情况，您必须在删除 之前tr将 的左孩子嫁接到的右侧。第二种情况稍微复杂一些。由于在不更改函数签名的情况下无法更改包含，因此无法删除传入的根节点。您必须通过复制其左子节点的值、重新链接其子节点并删除原来的左孩子。prevtrCTree

¹ 好吧，当然还有其他可用的方法，但我能想到的只是复制info和删除不同的节点。

于 2012-09-14T22:26:47.263 回答