Обход бинарного дерева по уровням - C++

447

01 июня 2017, 10:08

Кто может помочь реализовать обход бинарного дерева по уровням (уровень задаётся с клавиатуры)?

#include <iostream>
using namespace std;
// Наша структура
struct node {
    int info;  // Информационное поле
    node *l, *r;  // Левая и Правая часть дерева
};
node *tree = nullptr;  // Объявляем переменную, тип которой структура Дерево
node *tree1 = nullptr;  // Объявляем переменную, тип которой структура Дерево
// ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО
void push(int a, node **t) {
    if ((*t) == nullptr)  // Если дерева не существует
    {
        (*t) = new node;  // Выделяем память
        (*t)->info = a;  // Кладем в выделенное место аргумент a
        (*t)->l = (*t)->r = nullptr;  // Очищаем память для следующего роста
        return;  // Заложили семечко, выходим
    }
// Дерево есть
    if (a > (*t)->info)
        push(a, &(*t)->r);  // Если аргумент а больше чем текущий элемент, кладем его вправо
    else
        push(a, &(*t)->l);  // Иначе кладем его влево
}
// Функция сравнения двух деревьев
bool check(node *n1, node *n2) {
    return n1 && n2 ? n1->info == n2->info && check(n1->l, n2->l) && check(n1->r, n2->r) : !n1 && !n2;
}
// ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ
void print(node *t, int u) {
    if (t == nullptr)
        return;  // Если дерево пустое, то отображать нечего, выходим
    else {  // Иначе
        print(t->l, ++u);  // С помощью рекурсивного посещаем левое поддерево
        for (int i = 0; i < u; ++i)
            cout << "|";
        cout << t->info << endl;  // И показываем элемент
        u--;
        print(t->r, ++u);  // С помощью рекурсии посещаем правое поддерево
    }
}
int main() {
    setlocale(LC_ALL, "Russian");
    int n;  // Количество элементов
    int s;  // Число, передаваемое в дерево
    cout << "введите количество элементов\n";
    cin >> n;  // Вводим количество элементов
    for (int i = 0; i < n; ++i) {
        cout << "ведите число\n";
        cin >> s;  // Считываем элемент за элементом
        push(s, &tree);  // И каждый кладем в дерево
    }
    cout << "ваше дерево\n";
    print(tree, 0);
    return 0;
}

Answer 1

Ваша функция print делает почти то, что вы хотите. Надо лишь выполнять строчку cout << t->info << endl; только на нужном уровне. Например, так:

// Функция печатает уровень дерева на экран
void printLevel(node *t, int level) {
    if (t == nullptr) {
        // Если дерево пустое, то отображать нечего, выходим
        return;
    } else {
        printLevel(t->l, level - 1);  // С помощью рекурсии посещаем левое поддерево
        if (level == 0) {
            // level будет равен нулю на нужной глубине, так как при каждом рекурсивном вызове значение level уменьшается на один
            cout << t->info << endl;  // Показываем элемент, если он на нужном нам уровне
        }
        print(t->r, level - 1);  // С помощью рекурсии посещаем правое поддерево
    }
}