Обход дерева – центрированный (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 ->
Виртуальный хостинг со скидкой 10 процентов
Виртуальный хостинг со скидкой 10 процентов
EVILEG предлагает надёжный хостинг со скидкой 10% на виртуальный хостинг и 5% на VPS
Поддержать автора Donate

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
TT
13 июня 2019 г. 19:01
Taimoor Tanweer

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

  • Результат:66баллов,
  • Очки рейтинга-1
TT
13 июня 2019 г. 18:51
Taimoor Tanweer

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

  • Результат:75баллов,
  • Очки рейтинга2
ВМ
13 июня 2019 г. 12:30
Ваня Мороз

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

  • Результат:100баллов,
  • Очки рейтинга10
Последние комментарии
i
17 июня 2019 г. 6:10
ingenfly

Только по осям xAxis2, уAxis2 значения начинаются с 0. Почему-то xAxis2 и xAxis не синхронизированы по данным. Ну и QCustomPlot последний.
16 июня 2019 г. 20:21
Евгений Легоцкой

Добрый день. Ну точно также добавляете ту же самую информацию на ось xAxis2, только добавляете другое форматирование customPlot->xAxis2->setDateTimeFormat("hh:mm"); если я ...
EF
14 июня 2019 г. 13:56
Egor Fomin

Спасибо за ваш ответ, у меня получилось реализовать это. Тем не менее появилась другая проблема, поэтому опять надеюсь на вашу помощь. Скажем, я уже выставил точки и они соеденены. Когда я нач...
d
13 июня 2019 г. 14:47
damix

Можно классу, который описывает точку, добавить сигнал, который подавать (emit), когда точка перемещается (переопределить mouseMoveEvent или mouseReleaseEvent). Так вот эти сигналы у каждой из...
i
13 июня 2019 г. 14:09
ingenfly

Здравствайте! Подскажите, пожалуйста: customPlot->xAxis2->setTickLabels(true); //Здесь включается отображение данных на оси xAxis2. а можно как-то продублировать информацию cus...
Сейчас обсуждают на форуме
I
19 июня 2019 г. 13:41
Intruder

Всем добрый день. При разборе XML файла наткнулся на тег вот такого плана: <TagName attribute1="value1" attribute2="value2" /> При попытке проверить на наличие такого элеме...
19 июня 2019 г. 12:55
Михаиллл

Скажите пожалуйста, как его в таком случае перемещать и удалять?
18 июня 2019 г. 19:50
Дмитрий

Большое спасибо! SDK заработал.К сожалению удалось продвинутся только на один шаг. При сборке чистого проекта NDK выдаёт следующие ошибки C:\Android\ndk-bundle/toolchains/arm-linux-andr...
18 июня 2019 г. 16:59
Михаиллл

Добрый день.В этом учебнике представлен код INSTALLED_APPS = ( ... 'rest_framework', 'snippets.apps.SnippetsConfig',) На строчке 'snippets.apps.SnippetsConf...
18 июня 2019 г. 14:24
Михаиллл

Спасибо, работает.Послушаю вашего совета.
Ищу работу?
25,000.00 руб. - 30,000.00 руб.
Разработчик Qt/C++
Barnaul, Altai Krai, Russia

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

EVILEG
О нас
Услуги
Присоединяйтесь к нам
© EVILEG 2015-2019
Рекомендует хостинг TIMEWEB