Обхід дерева – центрований (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 ->