113. Коренови и двоични дървета
Кореновото дърво има избран корен. Всеки друг възел има един родител. Двоичното дърво има най-много две деца на възел, разграничени като ляво и дясно. Възел без деца е листо. При вмъкване, преместване или премахване трябва да пазим връзките родител–дете. При двоично представяне всеки възел може да пази две връзки, а при кореново дърво от общ вид може да пази списък с деца.
Раздел в разширената разработка.
Самостоятелна задача
Условие
В дърво на менюто коренът R има ляво дете A и дясно B. A има само дясно дете C. B и C нямат деца. Дълбочината е броят ребра по пътя от корена, а височината на дървото е най-голямата дълбочина.
- Кой е родителят на C?
- Кои са листата?
- Какви са дълбочината на C и височината на дървото?
- Ако R получи трето дете, какво свойство губи дървото?
Отговори за самопроверка
Отговор 1
A.
Отговор 2
B и C.
Отговор 3
И двете са 2, по пътя R–A–C.
Отговор 4
Губи свойството да е двоично. В кореново дърво са допустими три деца.
Изпълним пример
Примерът представя корен с две деца и показва лявото и дясното. Опитай да преместиш едното дете, като смениш връзките.
#include <iostream> // Включваме библиотеката, която ни дава cout за печат на екрана.
using namespace std; // Така можем да пишем cout вместо std::cout.
struct Node { // Описваме от какво се състои един възел.
char name; // Пазим името на възела като един знак.
Node* left; // Пазим адреса на лявото дете. Node* е указател към възел.
Node* right; // Пазим адреса на дясното дете.
}; // Край на описанието на типа.
int main() { // Оттук започва изпълнението на програмата.
Node left{'L', nullptr, nullptr}; // Създаваме лявото дете L. Двата празни адреса показват, че няма деца.
Node right{'R', nullptr, nullptr}; // Създаваме дясното дете R, също без деца.
Node root{'M', &left, &right}; // Създаваме корен M. С & подаваме адресите на двете му деца.
cout << root.name << ": " // Започваме изписването с името на корена и двоеточие.
<< root.left->name << ' ' << root.right->name << '\n'; // С -> вземаме и печатаме имената от двата адреса, които коренът пази.
} // Край на програмата.
В речника Кореново дърво · Двоично дърво · Листо (дърво) · Дълбочина и височина (дърво).