mafulechka
mafulechkaМаусым 3, 2019, 4:31 Т.Ж.

Ағаштың өтуі - орталықтандырылған (реттік), тікелей (алдын ала тапсырыс) және кері (постордер) (өтіп өтудің үш негізгі жолы)

Ағашты аралау ағаштың әрбір түйініне баруды білдіреді. Мысалы, ағашқа барлық мәндерді қосуға немесе ең үлкенін табуға болады. Барлық осы операциялар үшін ағаштың әрбір түйініне бару керек.


Массивтер, стектер, кезектер және байланыстырылған тізімдер сияқты сызықтық деректер құрылымдарында деректерді оқудың бір ғана жолы бар. Бірақ ағаш сияқты иерархиялық деректер құрылымын әртүрлі жолдармен өтуге болады.

Жоғарыда көрсетілген суреттегі ағаштың элементтерін қалай оқуға болатынын ойланайық.

Жоғарыдан бастап, солдан оңға қарай

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

Төменнен бастап, солдан оңға қарай

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

Бұл процесс біршама қарапайым болғанымен, ол ағаштың иерархиясын есепке алмайды, тек түйіндердің тереңдігін ескереді.

Оның орнына біз ағаштың негізгі құрылымын құрметтейтін өтпелі әдістерді қолданамыз, яғни.

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

сол (сол) және оң (оң) арқылы көрсетілген құрылымдық түйінде басқа сол және оң балалар болуы мүмкін, сондықтан біз оларды ішкі түйіндер емес, ішкі ағаштар ретінде қарастыруымыз керек.

Бұл құрылым бойынша әрбір ағаш комбинация болып табылады

  • Деректерді тасымалдайтын түйін
  • Екі ішкі ағаш

Біздің мақсатымыз әрбір түйінге бару екенін есте сақтаңыз, сондықтан бізге ішкі ағаштағы барлық түйіндерге бару, түбірлік түйінге бару, сонымен қатар оң жақ ішкі ағаштағы барлық түйіндерге бару керек.

Оны орындау ретіне байланысты үш түрлі өту болуы мүмкін.

Орталық өту түрі (ішкі ретпен өту)

  1. Алдымен сол жақ ішкі ағаштағы барлық түйіндерге барыңыз
  2. Содан кейін түбірлік түйін
  3. Оң жақ ішкі ағаштағы барлық түйіндерге барыңыз
inorder(root->left)
display(root->data)
inorder(root->right)

Тікелей өту түрі (Алдын ала тапсырыс бойынша өту)

  1. Түбірлік түйінге өтіңіз
  2. Сол жақ ішкі ағаштағы барлық түйіндерге кіріңіз
  3. Оң жақ ішкі ағаштағы барлық түйіндерге барыңыз
display(root->data)
preorder(root->left)
preorder(root->right)

Посторды өту

  1. сол жақ ішкі ағаштағы барлық түйіндерге барыңыз
  2. түбірлік түйінге барыңыз
  3. оң жақ ішкі ағаштағы барлық түйіндерге барыңыз
postorder(root->left)
postorder(root->right)
display(root->data)

Центрленген өту түрін көрейік. Түбірлік түйіннен бастайық.

Алдымен сол жақ ішкі ағашты айналып өтеміз. Сондай-ақ, ағаш дайын болған кезде түбірлік түйінге және оң жақ ішкі ағашқа баруды ұмытпауымыз керек.

Барлығын есте сақтау үшін стекке салайық.

Енді стектің жоғарғы жағында көрсетілген ішкі ағашқа көшейік.

Қайтадан, біз ортаңғы түрдегі бірдей ережені ұстанамыз (тәртіп)

Left subtree -> root -> right subtree

Сол жақ ішкі ағаштан өткеннен кейін біз қалдық

«5» түйінінде ішкі ағаштар болмағандықтан, біз оны тікелей басып шығарамыз. Осыдан кейін біз оның негізгі түйінін «12», содан кейін оның оң жақ еншісін «6» басып шығарамыз.

Барлығын стекке қою пайдалы болды, өйткені енді түбірлік түйіннің сол жақ ішкі ағашы өткеннен кейін оны басып шығарып, оң жақ ішкі ағашқа өтуге болады.

Барлық элементтерден өткеннен кейін орталықтандырылған өту түрі (тәртіптік өту) келесідей болады:

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

Бізге стекті өзіміз жасаудың қажеті жоқ, себебі рекурсия біз үшін дұрыс ретті сақтайды.

Си бағдарламалау тіліндегі орталықтандырылған (реттік), тікелей (алдын ала тапсырыс) және кері (постордер) өту түрінің толық коды төменде берілген:

#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 хостинг.

Ол саған ұнайды ма? Әлеуметтік желілерде бөлісіңіз!

Пікірлер

Тек рұқсаты бар пайдаланушылар ғана пікір қалдыра алады.
Кіріңіз немесе Тіркеліңіз
AD

C++ - Тест 004. Указатели, Массивы и Циклы

  • Нәтиже:50ұпай,
  • Бағалау ұпайлары-4
m
  • molni99
  • Қаз. 26, 2024, 1:37 Т.Ж.

C++ - Тест 004. Указатели, Массивы и Циклы

  • Нәтиже:80ұпай,
  • Бағалау ұпайлары4
m
  • molni99
  • Қаз. 26, 2024, 1:29 Т.Ж.

C++ - Тест 004. Указатели, Массивы и Циклы

  • Нәтиже:20ұпай,
  • Бағалау ұпайлары-10
Соңғы пікірлер
ИМ
Игорь МаксимовҚар. 22, 2024, 11:51 Т.Ж.
Django - Оқулық 017. Теңшелген Django кіру беті Добрый вечер Евгений! Я сделал себе авторизацию аналогичную вашей, все работает, кроме возврата к предидущей странице. Редеректит всегда на главную, хотя в логах сервера вижу запросы на правильн…
Evgenii Legotckoi
Evgenii LegotckoiҚаз. 31, 2024, 2:37 Т.Қ.
Django - Сабақ 064. Python Markdown кеңейтімін қалай жазуға болады Добрый день. Да, можно. Либо через такие же плагины, либо с постобработкой через python библиотеку Beautiful Soup
A
ALO1ZEҚаз. 19, 2024, 8:19 Т.Ж.
Qt Creator көмегімен fb3 файл оқу құралы Подскажите как это запустить? Я не шарю в программировании и кодинге. Скачал и установаил Qt, но куча ошибок выдается и не запустить. А очень надо fb3 переконвертировать в html
ИМ
Игорь МаксимовҚаз. 5, 2024, 7:51 Т.Ж.
Django - Сабақ 064. Python Markdown кеңейтімін қалай жазуға болады Приветствую Евгений! У меня вопрос. Можно ли вставлять свои классы в разметку редактора markdown? Допустим имея стандартную разметку: <ul> <li></li> <li></l…
d
dblas5Шілде 5, 2024, 11:02 Т.Ж.
QML - Сабақ 016. SQLite деректер қоры және онымен QML Qt-та жұмыс істеу Здравствуйте, возникает такая проблема (я новичок): ApplicationWindow неизвестный элемент. (М300) для TextField и Button аналогично. Могу предположить, что из-за более новой верси…
Енді форумда талқылаңыз
m
moogoҚар. 22, 2024, 7:17 Т.Ж.
Mosquito Spray System Effective Mosquito Systems for Backyard | Eco-Friendly Misting Control Device & Repellent Spray - Moogo ; Upgrade your backyard with our mosquito-repellent device! Our misters conce…
Evgenii Legotckoi
Evgenii LegotckoiМаусым 24, 2024, 3:11 Т.Қ.
добавить qlineseries в функции Я тут. Работы оень много. Отправил его в бан.
t
tonypeachey1Қар. 15, 2024, 6:04 Т.Ж.
google domain [url=https://google.com/]domain[/url] domain [http://www.example.com link title]
NSProject
NSProjectМаусым 4, 2022, 3:49 Т.Ж.
Всё ещё разбираюсь с кешем. В следствии прочтения данной статьи. Я принял для себя решение сделать кеширование свойств менеджера модели LikeDislike. И так как установка evileg_core для меня не была возможна, ибо он писался…

Бізді әлеуметтік желілерде бақылаңыз