реализовать очередь с использованием BST
Как мне реализовать Очередь, используя BST.
Если это способ сделать это, продолжайте вставлять узлы в дерево, сохраняя при этом значение счетчика, связанное с каждым и каждым узлом, но при удалении BST должен работать как очередь (FIFO), поэтому начните удаление из BST с узлом, имеющим наименьшее количество значение в дереве.
Правильно ли я понял вопрос и решение? Если нет, то, пожалуйста, объясните мне вопрос.
Решение
Вы можете иметь очередь, как это:
BST // to store data
pointer to head; // Points to the head of the Queue
pointer to tail // Points to the tail of the Queue
Вы добавляете к структурам узлов BST также указатель на другой узел, который будет представлять порядок вставки.
struct Node{
int x;
//left pointer
//right pointer
struct Node *next_queune_element;
}
Во время вставки
Когда вы хотите добавить элемент, вы сначала получаете доступ к узлу, на который указывает хвост указателя, и заставляете его указывать на новый элемент, который вы только что вставили (узел BST). Затем вы обновляете хвостовой указатель, чтобы он указывал на новый элемент.
Во время удаления
Когда вы удаляете элемент, вы сначала получаете доступ к узлу, на который указывает указатель головы, вы сохраняете next_queune_element во вспомогательной временной переменной и удалите узел. Наконец, сделайте указатель заголовка, чтобы указать на вспомогательную временную переменную.
Другие решения
BST — это действительно неподходящая структура данных, используемая для поддержки очереди. Вы действительно должны вместо этого использовать связанный список, потому что он был бы намного быстрее, менее сложным и просто лучше.
Однако, если вы настаиваете на использовании BST …
Вы должны использовать BST в качестве приоритетной очереди и определить тип оболочки, который также содержит «индекс очереди», по которому элементы будут отсортированы. Вы должны будете определить сравнение, чтобы принять во внимание текущий индекс очереди, потому что в противном случае вы могли бы добавить только столько элементов, сколько разница между самым высоким и самым низким значениями вашего типа индекса.
detector