Обход бинароного дерева в ширину, но с выводом конкретного урвня
Итак, постигаем программирование через C. Имеется код, который позволяет создать бинарное дерево в зависимости от количества первоначально заданных элементов, но вот возник вопрос, необходимо вывести элементы задаваемого уровня с клавиатуры (0,1,2, и т.д.) решая данную задачу пришёл к выводу, что стоит использовать обход дерева в ширину, но не могу понять как это реализовать правильно. Подскажите как этот кусочек этого кода
DblLinkedList* q = createDblLinkedList();
//Для начала поместим в очередь корень
push_Back(q, Node);
while (q->size != 0) {
Node* tmp = (Node*)popFront(q);
printf("%d ", tmp->data);
//Если есть левый наследник, то помещаем его в очередь для дальнейшей обработки
if (tmp->left) {
pushBack(q, tmp->left);
}
//Если есть правый наследник, то помещаем его в очередь для дальнейшей обработки
if (tmp->right) {
pushBack(q, tmp->right);
}
}
deleteDblLinkedList(&q);
}
вставить вот сюда:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <malloc.h>
#include <Windows.h>
typedef struct binarytree
{
int Data; //поле данных
binarytree* Left; //указатель на левого потомка
binarytree* Right; //указатель на правого потомка
} BinaryTree;
//создание бинарного дерева
void Create(BinaryTree** p, int x)
{
if (!(*p))//если указатель на корень дерева не равен NULL
{
BinaryTree* pnew = (BinaryTree*)
malloc(sizeof(BinaryTree));// выделяем память
pnew->Data = x; //заносим значение
pnew->Left = pnew->Right = NULL;
*p = pnew;
}
else
{
if ((*p)->Data > x)
Create(&((*p)->Left), x);
else
Create(&((*p)->Right), x);
}
}
/*Вывод двоичного дерева на экран*/
void Vyvod(BinaryTree** p, int l)
{
int i;
if (*p != NULL)
{
Vyvod(&((*p)->Right), l + 1);
for (i = 0; i < l; i++)
printf(" ");
printf("%d\n", (*p)->Data);
Vyvod(&((*p)->Left), l + 1);
}
}
/*Вывод k уровня на экран*/
/*Проверка пустоты дерева*/
bool empty_tree(BinaryTree* Node)
{
if (Node == NULL) return true;
else return false;
}
BinaryTree* Delete_BinaryTree(BinaryTree* Node) {
if (Node != NULL)
{
Delete_BinaryTree(Node->Left);
Delete_BinaryTree(Node->Right);
free(Node);
}
return NULL;
}
/* пытаемся найти уровень*/
void main() // главная функция
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
int i, n, temp,q;
BinaryTree* Root;
Root = NULL;
printf("Число элементов дерева\t");
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d", &temp);
Create(&Root, temp);
}
printf("Имеющееся дерево:\n");
Vyvod(&Root, 0);
printf("Какой уровень вывести?\t"); scanf("%d", &q);
if (empty_tree(Root))
{
printf("\nДерево пусто!\n");
_getch();
return;
}
Root = Delete_BinaryTree(Root);
if (empty_tree(Root))
printf("\nПамять очищена полностью!\n");
_getch();
return;
}
Ответы (1 шт):
Зачем вам городить огород с обходом в ширину - копить узлы в очереди, хранить информацию о глубине и всё такое? Простой обход в глубину решит вашу задачу легко и непринуждённо.
Не компилировано, не тестировано
/*
typedef struct binarytree
{
int Data; //поле данных
binarytree* Left; //указатель на левого потомка
binarytree* Right; //указатель на правого потомка
} BinaryTree;
*/
typedef void DataHandler(*BinaryTee bt);
void HandleLevel(*BinaryTree bt, unsigned int level, DataHandler dth) {
if (bt == NULL) {
return;
}
if (level == 0) {
dth(bt->data);
return;
}
HandLevel(bt->Left, level-1, dth);
HandLevel(bt->Right, level-1, dth);
}
Функция HandleLevel поднимается по дереву, одновременно отсчитывая, сколько "этажей" осталось пройти. Как только счётчик становится равным нулю, вызывается обработчик и подъём завершается.
Это тривиальнейший обход в глубину. Даже проще, так как благодаря структуре графа не нужно помечать пройденные вершины.
PS. Алгоритм по дереву таки поднимается, несмотря на то, что при традиционном способе изображения деревьев принято корень рисовать вверху, а листья внизу.