Форум на Исходниках.RU

Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=418172&view=findpost&p=3828462 Tue, 14 Apr 2020 13:01:19 +0000 Бинарное дерево поиска (горизонтальный обход) + queue(FIFO) https://forum.sources.ru/index.php?showtopic=418172&view=findpost&p=3828462 Цитата AVA12 @ 14.04.20, 12:50

Ты предлагаешь обход дерева в глубину, но раз в задании говорится про очередь и вывод дерева по уровням, значит нужен обход в ширину. Заводим очередь (односвязный список), в которой изначально лежит корневой узел дерева, затем в цикле берем первый узел из очереди, выводим его и добавляем в конец списка дочерние узлы (если есть) слева направо, повторяем, пока очередь не опустеет.

ааааааааааааа, вот оно как)
я чегот совсем забыл про "BFS" в деревьях, т к их не принято так обходить...

ну, значит, такие будут структуры данных:

1. элемент бинарки

struct TNode

{

int key;

TNode* left;

TNode* right;

};

2. элементы очереди

struct Telem

{

int key;

TElem* next;

int level; // вроде он тут нужен...хм...подумаю еще

};

спс AVA12]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=418172&view=findpost&p=3828459 Tue, 14 Apr 2020 12:50:31 +0000 Бинарное дерево поиска (горизонтальный обход) + queue(FIFO) https://forum.sources.ru/index.php?showtopic=418172&view=findpost&p=3828459 AVA12 Алгоритмы https://forum.sources.ru/index.php?showtopic=418172&view=findpost&p=3828455 Tue, 14 Apr 2020 12:19:25 +0000 Бинарное дерево поиска (горизонтальный обход) + queue(FIFO) https://forum.sources.ru/index.php?showtopic=418172&view=findpost&p=3828455
Задано бинарное дерево поиска. Нужно, используя структуру Queue(FIFO, очередь), сделать поуровневый обход с выводом на экран (горизонтальная печать дерева).

На рис. представлен пример бинарки + результат.
___________________________.png (, : 1107)

Мне непонятно здесь, как правильно задействовать очередь.

Что хочется сделать.
1. запустить симметричный обход дерева, записывая ключи дерева в очередь (ASC - по возрастанию).
Получится такая очередь: -10, 16, 17, 28, 29, 33, 50, 73, 86, 88, 90.

Также нужно дополнительно учесть уровень, на котором находится считываемый узел, поэтому запомним и эту информацию в элементах очереди:
Очередь из элементов: -10(2), 16(3), 17(1), 28(2), 29(4), 33(3), 50(0), 73(1), 86(3), 88(4), 90(2)

Прототип функции обхода дерева такой примерно:

void LKP(TElem* proot, int plevel); // proot - указатель на текущее поддерево, plevel - уровень обрабатываемого узла

В принципе, вот в принципе, дальше можно бегать по очереди и распечатывать сначала все узлы с уровнем = 0, затем все узлы с уровнем = 1 и т.д. Но во-первых, классическая очередь не имеет встроенной операции сканирования своих элементов (можно удалить из начала и вставить в конец), а во-вторых, зачем тогда сдалась очередь для подобной обработки - подошел бы простой одномерный массив (удобнее в разы, т к есть встроенный индексатор).

Подскажите, как правильно использовать ОЧЕРЕДЬ для решения поставленной задачи??

спс. за внимание]]> FasterHarder Алгоритмы