114. Обхождания на двоично дърво

При обхождане в предред обработваме възела преди децата. При средред го обработваме между лявото и дясното поддърво, а при следред — след двете.

Раздел в разширената разработка.

Самостоятелна задача

Условие

Дървото има корен A, ляво дете B и дясно C. B има само дясно дете D. C и D са листа. За всеки възел означаваме с В обработката на възела, с Л обхождането на лявото и с Д обхождането на дясното поддърво. Всеки от трите зададени реда се прилага и в поддърветата. Празно поддърво не добавя буква.

  1. Какъв е редът при В–Л–Д?
  2. Какъв е редът при Л–В–Д?
  3. Какъв е редът при Л–Д–В?
  4. Кой от тези редове обработва всяко дете преди родителя му?

Отговори за самопроверка

Отговор 1

A, B, D, C.

Отговор 2

B, D, A, C.

Отговор 3

D, B, C, A.

Отговор 4

Следред (Л–Д–В).

Изпълним пример

Премести реда с cout преди първото извикване или след второто, за да смениш реда на обхождане.

#include <iostream>                     // Включваме библиотеката, която ни дава cout за печат на екрана.
using namespace std;                    // Така можем да пишем cout вместо std::cout.

struct Node {                           // Описваме от какво се състои един възел.
    char name;                          // Пазим името на възела като един знак.
    Node* left;                         // Пазим адреса на лявото дете. Node* е указател към възел.
    Node* right;                        // Пазим адреса на дясното дете.
};                                      // Край на описанието на типа.

void visit(Node* node) {                // Функцията обхожда частта от дървото, която започва на подадения адрес.
    if (node == nullptr)                // Проверяваме дали адресът е празен.
        return;                         // Ако няма възел, приключваме това извикване.

    visit(node->left);                  // Първо извикваме същата функция за лявото дете.
    cout << node->name << ' ';          // След връщането печатаме името на текущия възел.
    visit(node->right);                 // Накрая извикваме същата функция за дясното дете.
}                                       // Край на функцията.

int main() {                            // Оттук започва изпълнението на програмата.
    Node left{'Q', nullptr, nullptr};   // Създаваме лявото дете Q без свои деца.
    Node right{'T', nullptr, nullptr};  // Създаваме дясното дете T без свои деца.
    Node root{'R', &left, &right};      // Създаваме корена R и записваме адресите на двете му деца.

    visit(&root);                       // Започваме обхождането от адреса на корена.
    cout << '\n';                       // След последното име минаваме на нов ред.
}                                       // Край на програмата.

Изтегли main.cpp.

В речника Обхождане на двоично дърво.