Обход порядка уровней в двоичном дереве

Обход по порядку уровней — это один из методов обхода бинарного дерева. В этой статье мы рассмотрим, как реализовать этот алгоритм на C/C++.

Но перед этим давайте рассмотрим наши концепции.

Построение концепций

Двоичное дерево — это структура данных, в которой каждый узел имеет не более двух дочерних элементов. Самый верхний узел называется корневым узлом.

Существует 4 распространенных способа обхода узлов бинарного дерева, а именно:

По порядку обхода
Обход предварительного заказа
Обход после заказа
Обход порядка уровней

Давайте разберемся, что означает уровень в бинарном дереве.

Уровень — это количество родительских узлов, соответствующих данному узлу дерева. По сути, это количество предков от этого узла до корневого узла.

Итак, для корневого узла (самого верхнего узла) его уровень равен 0, так как у него нет родителей. Если у него есть потомки, они оба будут иметь уровень 1, так как у него есть только один предок до корневого узла, которым является сам корневой узел.

Нам также необходимо понять понятие высоты в двоичном дереве. Это просто длина пути от корня до самого глубокого узла в дереве.

В этом случае высотой будет длина от самого глубокого узла (40 или 50, так как у них максимальный уровень) до корня. Итак, высота дерева равна 2.

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

Обход порядка уровней

Обход по порядку уровней — это обход, который всегда проходит на основе уровня дерева.

Таким образом, этот обход сначала проходит через узлы, соответствующие уровню 0, затем уровню 1 и так далее от корневого узла.

В приведенном выше примере двоичного дерева порядок обхода уровней будет следующим:

(корень) 10 -> 20 -> 30 -> 40 -> 50

Для этого нам нужно сделать 2 вещи.

Сначала нужно найти высоту дерева
Нам нужно найти способ распечатать узлы, соответствующие каждому уровню.

Найдите высоту Дерева

Сначала найдем высоту дерева. Для этого логика проста.

Так как высота дерева определяется как наибольший путь от корня до листа. Таким образом, мы можем рекурсивно вычислить высоту левого и правого поддеревьев и найти максимальную высоту поддерева. Тогда высота дерева будет просто высотой поддерева + 1.

Псевдокод в стиле C:

// Find height of a tree, defined by the root node
int tree_height(Node* root) {
    if (root == NULL) 
        return 0;
    else {
        // Find the height of left, right subtrees
        left_height = tree_height(root->left);
        right_height = tree_height(root->right);
        
        // Find max(subtree_height) + 1 to get the height of the tree
        return max(left_height, right_height) + 1;
}

Распечатать все узлы на каждом уровне

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

void print_tree_level_order(Node* root) {
    int height = tree_height(root);
    for (int i=0; i<height; i++) {
        // Print the ith level
        print_level(root, i);
    }
}

Обратите внимание, что нам нужна еще одна функция для вывода i-го уровня дерева.

Здесь опять аналогичная логика. Но на этот раз, после печати корневого узла, мы меняем корневой узел на его левого и правого дочерних элементов и печатаем оба поддерева.

Это будет продолжаться до тех пор, пока мы не достигнем листового узла, то есть когда вспомогательный корень будет NULL на следующем шаге. (Поскольку leaf_node->left=NULL и leaf_node->right=NULL)

void print_level(Node* root, int level_no) {
    // Prints the nodes in the tree
    // having a level = level_no
    
    // We have a auxiliary root node
    // for printing the root of every
    // sub-tree
    if (!root)
        return;
    if (level_no == 0) {
        // We are at the top of a sub-tree
        // So print the auxiliary root node
        printf("%d -> ", root->value);
    }
    else {
        // Make the auxiliary root node to
        // be the left and right nodes for
        // the sub-trees and decrease level by 1, since
        // you are moving from top to bottom
        print_level(root->left, level_no - 1);
        print_level(root->right, level_no - 1);
    }

}

Итак, мы наконец-то завершили обход порядка уровней!

Ниже я приведу полную программу, в которой также есть раздел для построения двоичного дерева с использованием вставки.

Полный код C/C++

Хотя изначально это программа на C, ее можно скомпилировать и на C++.

/**
    Code for https://journaldev.com
    File Name: level_order.c
    Purpose: Find the Level Order Traversal of a Binary Tree

    @author Vijay Ramachandran
    @date 28/01/2020
*/

#include <stdio.h>
#include <stdlib.h>

typedef struct Node Node;

// Define the Tree Node here
struct Node {
    int value;
    // Pointers to the left and right children
    Node* left, *right;
};


Node* init_tree(int data) {
    // Creates the tree and returns the
    // root node
    Node* root = (Node*) malloc (sizeof(Node));
    root->left = root->right = NULL;
    root->value = data;
    return root;
}

Node* create_node(int data) {
    // Creates a new node
    Node* node = (Node*) malloc (sizeof(Node));
    node->value = data;
    node->left = node->right = NULL;
    return node;
}

void free_tree(Node* root) {
    // Deallocates memory corresponding
    // to every node in the tree.
    Node* temp = root;
    if (!temp)
        return;
    free_tree(temp->left);
    free_tree(temp->right);
    if (!temp->left && !temp->right) {
        free(temp);
        return;
    }
}

int tree_height(Node* root) {
    // Get the height of the tree
    if (!root)
        return 0;
    else {
        // Find the height of both subtrees
        // and use the larger one
        int left_height = tree_height(root->left);
        int right_height = tree_height(root->right);
        if (left_height >= right_height)
            return left_height + 1;
        else
            return right_height + 1;
    }
}

void print_level(Node* root, int level_no) {
    // Prints the nodes in the tree
    // having a level = level_no
    
    // We have a auxiliary root node
    // for printing the root of every
    // subtree
    if (!root)
        return;
    if (level_no == 0) {
        // We are at the top of a subtree
        // So print the auxiliary root node
        printf("%d -> ", root->value);
    }
    else {
        // Make the auxiliary root node to
        // be the left and right nodes for
        // the subtrees and decrease level by 1, since
        // you are moving from top to bottom
        print_level(root->left, level_no - 1);
        print_level(root->right, level_no - 1);
    }

}

void print_tree_level_order(Node* root) {
    if (!root)
        return;
    int height = tree_height(root);
    for (int i=0; i<height; i++) {
        printf("Level %d: ", i);
        print_level(root, i);
        printf("\n");
    }
    printf("\n\n-----Complete Level Order Traversal:-----\n");
    for (int i=0; i<height; i++) {
        print_level(root, i);
    }
    printf("\n");
}

int main() {
    // Program to demonstrate Level Order Traversal

    // Create the root node having a value of 10
    Node* root = init_tree(10);
    
    // Insert nodes onto the tree
    root->left = create_node(20);
    root->right = create_node(30);
    root->left->left = create_node(40);
    root->left->right = create_node(50);
    
    // Level Order Traversal
    print_tree_level_order(root);

    // Free the tree!
    free_tree(root);
    return 0;
}

Выход

Level 0: 10 -> 
Level 1: 20 -> 30 -> 
Level 2: 40 -> 50 -> 


-----Complete Level Order Traversal:-----
10 -> 20 -> 30 -> 40 -> 50 ->

Вы также можете скачать это через Github gist, который я создал для этой цели. (Также содержит код для вставки)

Заключение

Надеюсь, вы лучше понимаете, как можно реализовать обход порядка уровней в C/C++. Если у вас есть какие-либо вопросы, не стесняйтесь задавать их в разделе комментариев ниже!