114. Обхождания на двоично дърво
При обхождане в предред обработваме възела преди децата. При средред го обработваме между лявото и дясното поддърво, а при следред — след двете.
Раздел в разширената разработка.
Самостоятелна задача
Условие
Дървото има корен A, ляво дете B и дясно C. B има само дясно дете D. C и D са листа. За всеки възел означаваме с В обработката на възела, с Л обхождането на лявото и с Д обхождането на дясното поддърво. Всеки от трите зададени реда се прилага и в поддърветата. Празно поддърво не добавя буква.
- Какъв е редът при В–Л–Д?
- Какъв е редът при Л–В–Д?
- Какъв е редът при Л–Д–В?
- Кой от тези редове обработва всяко дете преди родителя му?
Отговори за самопроверка
Отговор 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'; // След последното име минаваме на нов ред.
} // Край на програмата.
В речника Обхождане на двоично дърво.