Использовать двоичное дерево в шаблоне как приоритетную очередь - PullRequest
Новая
       26

Использовать двоичное дерево в шаблоне как приоритетную очередь

0 голосов
/ 18 ноября 2011

Итак, я хочу создать код, который создает двоичное дерево, в котором хранятся данные, например, целые числа типа 1,6,2,10,8, а в pop я получаю наибольшее число, и после этого оно удаляется издерево, и на толчок я могу вставить новый элемент.И это должно быть в шаблоне, чтобы я мог легко изменить тип данных, которые я хочу сохранить в дереве.Теперь у меня есть дерево, без шаблона оно работает нормально, я могу добавлять элементы и печатать их, но когда я пытаюсь поместить его в шаблон, я получаю следующую ошибку: использование шаблона класса требует шаблонасписок аргументов.В чем может быть проблема?Может быть, я делаю это совершенно неправильно.Любые предложения приветствуются.

Это был мой первый вопрос, который был исправлен avakar ty.(я опубликую код в конце моего вопроса)

Я только что прочитал через запрос проекта, и это похоже на то, я должен сделать это выше в первой части описанного вопроса, но это похоже надвоичное дерево должно представлять приоритетную очередь.И именно поэтому в запросе написано, что я должен использовать push, чтобы поместить новый элемент в дерево в порядке приоритета, и с помощью pop я получу элемент с наивысшим приоритетом, а затем этот элемент будет удален.Итак, как я могу использовать свое дерево в качестве приоритетной очереди, или он уже один (думаю, нет, но кто знал)?Я надеюсь, что смогу это объяснить.

А вот код, как обещано: 

#include <iostream>


using namespace std;


template<class T>
class BinaryTree
{
struct Node
    {
        T data;
        Node* lChildptr;
        Node* rChildptr;

        Node(T dataNew)
        {
            data = dataNew;
            lChildptr = NULL;
            rChildptr = NULL;
        }
    };
private:
    Node* root; 

        void Insert(T newData, Node* &theRoot)
        {
            if(theRoot == NULL)
            {
                theRoot = new Node(newData);
                return;
            }

            if(newData < theRoot->data)
                Insert(newData, theRoot->lChildptr);
            else
                Insert(newData, theRoot->rChildptr);;
        }

        void PrintTree(Node* theRoot)
        {
            if(theRoot != NULL)
            {
                PrintTree(theRoot->lChildptr);
                cout<< theRoot->data<<" ";;
                PrintTree(theRoot->rChildptr);
            }
        }

    public:
        BinaryTree()
        {
            root = NULL;
        }

        void AddItem(T newData)
        {
            Insert(newData, root);
        }

        void PrintTree()
        {
            PrintTree(root);
        }
    };

    int main()
    {
        BinaryTree<int> *myBT = new BinaryTree<int>();
        myBT->AddItem(1);
        myBT->AddItem(7);
        myBT->AddItem(1);
        myBT->AddItem(10);
        myBT->AddItem(4);
        myBT->PrintTree();
    }

Ответы [ 2 ]

1 голос
/ 18 ноября 2011

Если вы хотите использовать двоичное дерево в качестве приоритетной очереди, вы извлекаете максимальный элемент, шагая только через правые дочерние указатели.Любой оставленный дочерний элемент будет меньше, чем текущий элемент.Таким образом, вы записываете значение этого узла, а затем удаляете его - вам все равно придется написать подпрограмму удаления узла.

Проблема с простым BST заключается в том, что он может стать несбалансированным и отправить ваши сложности в O (п).Вы можете использовать самобалансирующийся BST, но это непривычно для очередей с приоритетом.Как сказал Керрек, вместо BST они обычно составляют кучи .

Самая простая реализация кучи, которую я знаю лично, - это двоичная куча .Бинарная куча теоретически является типом двоичного дерева, хотя и не хранится как таковая.Таким образом, в зависимости от того, нужно ли вам реализовать BST или просто двоичное дерево, оно может соответствовать вашим требованиям.

1 голос
/ 18 ноября 2011

На этой строке: 

BinaryTree<int> *myBT = new BinaryTree();

Вам также необходимо указать тип шаблона, который вы хотите создать, в правой части задания: 

BinaryTree<int> *myBT = new BinaryTree<int>();

Потому что BinaryTree не является BinaryTree<int>; один - это имя шаблона (BinaryTree), а другой - имя определенного типа этого шаблона (BinaryTree<int>). Вы не можете создавать экземпляры простых шаблонов, вы должны указать тип шаблона, который хотите использовать постоянно.

...