2

データ構造クラスに二分探索木を利用する優先キューを作成しました。それが生成する出力は、一部の入力では正しく、他の入力では正しくありません。 正しい出力：

要素数を入力してください：5

5の1を入力してください：1

5の2番を入力してください：2

5の3番を入力してください：3

5の4番を入力してください：4

5の5番を入力してください：5

5の番号1を出力：5

5の2番を出力：4

5の番号3を出力：3

5の番号4を出力：2

5の5番を出力：1

何かキーを押すと続行します 。。。

正しくない出力

要素数を入力してください：5

5の番号1を入力してください：-56

5の2番を入力してください：4

5の3番を入力してください：56

5の4番を入力してください：21

5の5番を入力してください：32

5の1を出力：56

5の2番を出力：4

5の番号3を出力：-56

5の番号4を出力：-56

5の5番を出力：-56

何かキーを押すと続行します 。。。

Test.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、の左の子をの右に接ぎ木する必要があります。2番目のケースはもう少し複雑です。関数のシグネチャを変更せずに包含を変更することはできないため、渡されたルートノードを削除することはできません。左の子の値をコピーし、その子を再リンクして、元の左の子。prevtrCTree

¹もちろん、他にも利用できる方法がありますが、私が考えることができるのはinfo、別のノードをコピーして削除することだけです。

于 2012-09-14T22:26:47.263 に答える