2015-09-06
283
Ці три методи можна сформулювати у вигляді рекурсивних алгоритмів.
void Run (point * p)
/ / Обхід зліва направо
{
If (p)
{
<Обробка p-> data>Run (p-> left);/ / перехід до лівого піддерева
Run (p-> right);/ / перехід до правого піддерева
}
}
Якщо в якості операції обробки вузла поставити операцію виведення інформаційного поля, то ми отримаємо функцію для друку дерева.
Формування дерева
/ / Побудова дерева пошуку
Point * first (int d) / / формування першого елемента дерева
{
Point * p = new Point;
p-> key = d;
p-> left = 0;
p-> right = 0;
return p;
}
/ / Додавання елемента d в дерево пошуку
Point * Add (Point * root, int d)
{
Point * p = root;/ / корінь дерева
Point * r;
/ / Прапор для перевірки існування елемента d в дереві
bool ok = false;
while (p &&! ok)
{
r = p;
if (d == p-> key) ok = true;/ / елемент вже існує
Else
if (d <p-> key) p = p-> left;/ / піти в ліве піддерево
else p = p-> right;/ / піти в праве піддерево
}
If (ok) return p;/ / знайдено, не додаємо
/ / Створюємо вузол
Point * New_point = new Point ();/ / виділили пам'ять
New_point-> key = d;
New_point-> left = 0;New_point-> right = 0;
/ / Якщо d <r-> key, то додаємо його в ліве піддерево
|
|
|
if (d <r-> key) r-> left = New_point;
/ / Якщо d> r-> key, то додаємо його в праве піддерево
else r-> right = New_point;return New_point;
}
/ / Побудова ідеально збалансованого дерева
point * Tree (int n, point * p)
{
point * r;
int nl, nr;
if (n == 0) {p = NULL; return p;}
nl = n / 2;
nr = n-nl-1;
r = new point;
cout << "?";
cin >> r-> data;
r-> left = Tree (nl, r-> left);r-> right = Tree (nr, r-> right);
p = r;
return p;
}
Постановка завдання
Сформувати односпрямований список, тип інформаційного поля зазначений у варіанті.
Роздрукувати отриманий список.
Виконати обробку списку у відповідності з завданням.
Роздрукувати отриманий список.
Видалити список з пам'яті.6. Сформувати двонаправлений список, тип інформаційного поля зазначений у варіанті.
Роздрукувати отриманий список.
Виконати обробку списку у відповідності з завданням.
Роздрукувати отриманий список.
Видалити список з пам'яті.
Сформувати ідеально збалансоване бінарне дерево, тип інформаційного поля зазначений у варіанті.
Роздрукувати отримане дерево.
Виконати обробку дерева відповідно до завдання, вивести отриманий результат.
Перетворити ідеально збалансоване дерево в дерево пошуку.
Роздрукувати отримане дерево.
