Обход дерева – центрированный (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 ->
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
TT
June 13, 2019, 7:01 p.m.
Taimoor Tanweer

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

  • Result:66points,
  • Rating points-1
TT
June 13, 2019, 6:51 p.m.
Taimoor Tanweer

C++ - Test 002. Constants

  • Result:75points,
  • Rating points2
ВМ
June 13, 2019, 12:30 p.m.
Ваня Мороз

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

  • Result:100points,
  • Rating points10
Last comments
i
June 17, 2019, 6:10 a.m.
ingenfly

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

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

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

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

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

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

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

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

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

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

For registered users on the site there is a minimum amount of advertising

EVILEG
About
Services
Join us
© EVILEG 2015-2019
Recommend hosting TIMEWEB