113. Коренови и двоични дървета

Кореновото дърво има избран корен. Всеки друг възел има един родител. Двоичното дърво има най-много две деца на възел, разграничени като ляво и дясно. Възел без деца е листо. При вмъкване, преместване или премахване трябва да пазим връзките родител–дете. При двоично представяне всеки възел може да пази две връзки, а при кореново дърво от общ вид може да пази списък с деца.

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

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

Условие

В дърво на менюто коренът R има ляво дете A и дясно B. A има само дясно дете C. B и C нямат деца. Дълбочината е броят ребра по пътя от корена, а височината на дървото е най-голямата дълбочина.

  1. Кой е родителят на C?
  2. Кои са листата?
  3. Какви са дълбочината на C и височината на дървото?
  4. Ако 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';  // С -> вземаме и печатаме имената от двата адреса, които коренът пази.
}                                                         // Край на програмата.

Изтегли main.cpp.

В речника Кореново дърво · Двоично дърво · Листо (дърво) · Дълбочина и височина (дърво).