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

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

Content

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

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

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

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

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 ->
We recommend hosting TIMEWEB
We recommend hosting TIMEWEB
Stable hosting, on which the social network EVILEG is located. For projects on Django we recommend VDS hosting.
Support the author Donate

Comments

Only authorized users can post comments.
Please, Log in or Sign up
How to become an author?

Contribute to the evolution of the EVILEG community.

Learn how to become a site author.

Learn it
Donate

Good day, Dear Users!!!

I am Evgenii Legotckoi, developer of EVILEG. And it is my hobby project, which helps to learn programming another programmers and developers

If the site helped you, and you want also support the development of the site, than you can donate by following ways

PayPalYandex.Money
Timeweb

Let me recommend you the excellent hosting on which EVILEG is located.

For many years, Timeweb has been proving his stability.

For projects on Django I recommend VDS hosting

View Hosting Timeweb
MN
May 25, 2020, 11:33 a.m.
Mitja Nagibin

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:50points,
  • Rating points-4
f
May 25, 2020, 5:05 a.m.
falcon

C++ - Test 001. The first program and data types

  • Result:66points,
  • Rating points-1
jm
May 25, 2020, 3:30 a.m.
just maks

C ++ - Test 004. Pointers, Arrays and Loops

  • Result:80points,
  • Rating points4
Last comments
May 26, 2020, 6:51 a.m.
Evgenij Legotskoj

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

У вас база данных не открылась Исправьте путь к базе данных на свой корректный в следующих методах void DataBase::connectToDataBase() bool DataBase::openDataBase()
T1
T1
May 26, 2020, 6:22 a.m.
Tima 1

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

полностью повторил структору проекта. В форму дабавил tableView. Но при запуске получаю форму только с пустым tableView. Можете подсказать в чем пробелма?
May 26, 2020, 6:02 a.m.
Evgenij Legotskoj

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

Потому что это файл который нужно создать, а не библиотека. В статье есть содержание этого файла. Добавляйте в проект. Копируйте содержимое из статьи.
T1
May 26, 2020, 6 a.m.
Tima 1

Qt/C++ - Lesson 004. QSqlTableModel – How to present the table from database?

не удается подключиить библеотеку include "database.h" выдает ошибку. Можете помочь?
Now discuss on the forum
May 26, 2020, 5:16 a.m.
BlinCT

Отсутствие драйвера SQLite в пакете Qt 4 на Linux

Вот честно непонимаю почему до сих пор используют qt4, там же столько всего отсутствует, много фишек и возможностей нету там. То есть используя такое старье приходится много писать самому а не и…
DK
May 26, 2020, 2:24 a.m.
Dzhon Kofi

Disable autoscroll

такие естественные решения все перепробовал. Получилось вчера так: const int maximumScroll = ui->_samples->verticalScrollBar()->maximum();const int sliderPos = ui->_samp…
May 26, 2020, 12:43 a.m.
Ruslan Polupan

Посоветуйте новичку (базы данных и Qt, что учить)

Без БД сейчас практически никуда. Поэтому SQL надо знать. SQLite самы простой вариант, но имхо лучще начать с бд клиент-сервер. Настроить сервер. Подключаться клиентом. Просто это помогает понят…
EJ
May 25, 2020, 2:42 p.m.
Esteban José María

Компиляция пустого проекта Qt Android

qt 5.12.8 BUILD SUCCESSFUL in 42s 28 actionable tasks: 28 executed Android package built successfully in 68.251 ms. Ну, буду разбираться по-тихоньку. :)
s
May 25, 2020, 1:24 p.m.
sander-007

Использование файлов в памяти (memory file mapping)

Добрый вечер, проблемы работы с файлом Exel нет вообще. Весь смысл в том чтобы не создавать на диске физический файл (требования безопасности), дабы потом не чистить. А так вопрос только в этом …
About
Services
© EVILEG 2015-2020
Recommend hosting TIMEWEB