Обход дерева – центрированный (inorder), прямой (preorder) и обратный (postorder) (три основных способа обхода)

Алгоритм, Tree, Дерево

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

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

Давайте подумаем о том, как мы можем прочитать элементы дерева на изображении, показанном выше.

Начиная сверху, слева направо

1 -> 12 -> 9 -> 5 -> 6

Начиная снизу, слева направо

5 -> 6 -> 12 -> 9 -> 1

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

Вместо этого мы используем методы обхода, которые учитывают базовую структуру дерева, то есть

struct node {
    int data;
    struct node* left;
    struct node* right;
}

Узел структуры, на который указывают left (левый) и right (правый) , может иметь другие левые и правые дочерние элементы, поэтому мы должны рассматривать их как поддеревья, а не подузлы.

Согласно этой структуре каждое дерево представляет собой комбинацию

  • Узел, несущий данные
  • Два поддерева

Помните, что нашей задачей является посещение каждого узла, поэтому нам нужно посетить все узлы в поддереве, посетить корневой узел и также посетить все узлы в правом поддереве.

В зависимости от порядка, в котором мы это делаем, может быть три типа обхода .

Центрированный тип обхода (Inorder traversal)

  1. Сначала посетите все узлы в левом поддереве
  2. Затем корневой узел
  3. Посетите все узлы в правом поддереве
inorder(root->left)
display(root->data)
inorder(root->right)

Прямой тип обхода (Preorder traversal)

  1. Посетите корневой узел
  2. Посетите все узлы в левом поддереве
  3. Посетите все узлы в правом поддереве
display(root->data)
preorder(root->left)
preorder(root->right)

Обратный тип обхода (Postorder traversal)

  1. посетить все узлы в левом поддереве
  2. посетить корневой узел
  3. посетить все узлы в правом поддереве
postorder(root->left)
postorder(root->right)
display(root->data)

Давайте визуализируем центрированный тип обхода (inorder traversal). Начнем с корневого узла.

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

Давайте поместим все это в стек, чтобы мы помнили.

Теперь перейдем к поддереву, указанному на вершине стека.

Опять же, мы следуем тому же правилу центрированного типа (inorder)

Left subtree -> root -> right subtree

Пройдя левое поддерево, мы остаемся с

Поскольку у узла "5" нет поддеревьев, мы печатаем его напрямую. После этого мы печатаем его родительский узел «12», а затем правый дочерний «6».

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

После прохождения всех элементов, центрированный тип обхода (inorder traversal) выглядит так:

5 -> 12 -> 6 -> 1 -> 9

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

Полный код для центрированного (inorder), прямого (preorder) и обратного (postorder) типа обхода на языке программирования C размещен ниже:

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

struct node {
    int data;
    struct node* left;
    struct node* right;
};

void inorder(struct node* root){
    if(root == NULL) return;
    inorder(root->left);
    printf("%d ->", root->data);
    inorder(root->right);
}

void preorder(struct node* root){
    if(root == NULL) return;
    printf("%d ->", root->data);
    preorder(root->left);
    preorder(root->right);
}

void postorder(struct node* root) {
    if(root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ->", root->data);
}


struct node* createNode(value){
    struct node* newNode = malloc(sizeof(struct node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

struct node* insertLeft(struct node *root, int value) {
    root->left = createNode(value);
    return root->left;
} 


struct node* insertRight(struct node *root, int value){
    root->right = createNode(value);
    return root->right;
}


int main(){
    struct node* root = createNode(1);
    insertLeft(root, 12);
    insertRight(root, 9);

    insertLeft(root->left, 5);
    insertRight(root->left, 6);

    printf("Inorder traversal \n");
    inorder(root);

    printf("\nPreorder traversal \n");
    preorder(root);

    printf("\nPostorder traversal \n");
    postorder(root);
}

Вывод кода будет выглядеть так:

Inorder traversal                                                                                                                                                         
5 ->12 ->6 ->1 ->9 ->                                                                                                                                                     
Preorder traversal                                                                                                                                                        
1 ->12 ->5 ->6 ->9 ->                                                                                                                                                     
Postorder traversal                                                                                                                                                       
5 ->6 ->12 ->9 ->1 ->
Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.
Поддержать автора Donate

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
Ищу работу?
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

Для зарегистрированных пользователей на сайте присутствует минимальное количество рекламы

s
18 сентября 2019 г. 17:19
sanyalitv

C++ - Тест 002. Константы

  • Результат:33баллов,
  • Очки рейтинга-10
s
18 сентября 2019 г. 17:12
sanyalitv

C++ - Тест 001. Первая программа и типы данных

  • Результат:80баллов,
  • Очки рейтинга4
d
18 сентября 2019 г. 7:34
dbuzin

C++ - Тест 001. Первая программа и типы данных

  • Результат:33баллов,
  • Очки рейтинга-10
Последние комментарии
M
20 сентября 2019 г. 11:25
Mark

вызываю метод get у m_downloader в другом методе и приложение начинает вылетать. В чем ошибка?
M
19 сентября 2019 г. 5:45
Mark

А вот как выгрузить файл на сервер по http протоколу? Допустим на regRu. И как получить путь файла, которой отображается в файловом менеджере regRu, чтобы загрузить его.
17 сентября 2019 г. 6:07
Misha Lebedev

Кстати интересные темы нашёл тут https://emacsway.github.io/ru/django-framework/#django-models Может что полезного тоже Евгений найдёте
17 сентября 2019 г. 4:50
Misha Lebedev

Доброго времени суток. Спасибо за хороший ответ, У меня ситуация така что в галлереи будет несколько миллионов фотографий с фильтрами и тегами , и я опасаюсь за производительност . Это ос…
17 сентября 2019 г. 3:23
Евгений Легоцкой

Добрый день. Да, я тоже читал ту статью в своё время и согласен с тем, что внешние ключи гораздо лучше, чем GenericForeignKey. Выборки в ряде случае работают быстрее. Но лично мне про…
Сейчас обсуждают на форуме
20 сентября 2019 г. 4:56
Pavel K.

Привет , подскажите кто-нибудь , как сделать драг н дроп , не нарушая при этом логику работы зума? import QtQuick 2.6 import QtGraphicalEffects 1.0 Page { id:win property string fi…
19 сентября 2019 г. 8:03
Михаиллл

Скопировал базу в папку пользователей и тогда получилось записывать в нее
19 сентября 2019 г. 5:32
Михаиллл

Но мне же нужно еще получить этот id и вернуть его пользователю, а при таком запросе ничего не вернется.
M
18 сентября 2019 г. 17:35
Mark

Понятно Тогда можно ли достать только параметры файла? Например только дату его изменения
p
17 сентября 2019 г. 5:02
pstMem

Да, действительно нужно дебажить, по другому не словить исключение. Уже решил проблему, был выход за предел массива, не правильные входные данные, так что всегда проверяйте размер массива.
EVILEG
О нас
Услуги
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB