Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.149.229.253] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
Задано бинарное дерево поиска. Нужно, используя структуру Queue(FIFO, очередь), сделать поуровневый обход с выводом на экран (горизонтальная печать дерева). На рис. представлен пример бинарки + результат. Прикреплённая картинка
Мне непонятно здесь, как правильно задействовать очередь. Что хочется сделать. 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 и т.д. Но во-первых, классическая очередь не имеет встроенной операции сканирования своих элементов (можно удалить из начала и вставить в конец), а во-вторых, зачем тогда сдалась очередь для подобной обработки - подошел бы простой одномерный массив (удобнее в разы, т к есть встроенный индексатор). Подскажите, как правильно использовать ОЧЕРЕДЬ для решения поставленной задачи?? спс. за внимание |
Сообщ.
#2
,
|
|
|
Ты предлагаешь обход дерева в глубину, но раз в задании говорится про очередь и вывод дерева по уровням, значит нужен обход в ширину. Заводим очередь (односвязный список), в которой изначально лежит корневой узел дерева, затем в цикле берем первый узел из очереди, выводим его и добавляем в конец списка дочерние узлы (если есть) слева направо, повторяем, пока очередь не опустеет.
|
Сообщ.
#3
,
|
|
|
Цитата AVA12 @ Ты предлагаешь обход дерева в глубину, но раз в задании говорится про очередь и вывод дерева по уровням, значит нужен обход в ширину. Заводим очередь (односвязный список), в которой изначально лежит корневой узел дерева, затем в цикле берем первый узел из очереди, выводим его и добавляем в конец списка дочерние узлы (если есть) слева направо, повторяем, пока очередь не опустеет. ааааааааааааа, вот оно как) я чегот совсем забыл про "BFS" в деревьях, т к их не принято так обходить... ну, значит, такие будут структуры данных: 1. элемент бинарки struct TNode { int key; TNode* left; TNode* right; }; 2. элементы очереди struct Telem { int key; TElem* next; int level; // вроде он тут нужен...хм...подумаю еще }; спс AVA12 |