1.Запустите IDE Borland C++ 5.02. Подготовьте запуск исполнимых файлов в консольном режиме.
2.Откомпилируйте и запустите предложенную программу, иллюстрирующую построение идеально сбалансированного дерева(рекурсивный алгоритм).
#include<iostream.h>struct node{ int Key; int Count; node *Left; node *Right;}; class TREE{ private: node *duk; //Корень дерева. public: TREE() { duk = NULL; } node **GetDuk() { return &duk; } node *Tree (int, node **); void Vyvod (node **, int);}; void main (){ TREE A; int n; cout<<"Введите количество вершин -...\n"; cin>>n; cout<<"Вводите ключи...\n"; A.Tree (n,A.GetDuk()); A.Vyvod (A.GetDuk(),0);} node *TREE::Tree (int n,node **p)// Построение идеально сбалансированного// дерева с n вершинами.// *p - указатель на корень дерева.{ node *now; int x,nl,nr; now = *p; if (n==0) *p = NULL; else { nl = n/2; nr = n - nl - 1; cin>>x; now = new(node); (*now).Key = x; Tree (nl,&((*now).Left)); Tree (nr,&((*now).Right)); *p = now; }} void TREE::Vyvod (node **w,int l)// Изображение бинарного дерева, заданного// указателем *w на экране дисплея.{ if (*w!=NULL) { Vyvod (&((**w).Right),l+1); for (int i=1; i<=l; i++) cout<<" "; cout<<(**w).Key<<endl; Vyvod (&((**w).Left),l+1); }}
Простота и ясность этой программы, достигается благодаря использованию рекурсивных процедур. Рекурсивные алгоритмы особенно уместны, когда программа должна обрабатывать данные, структура которых определена рекурсивно.
Пусть имеется следующий набор ключей для построения дерева с 21 вершиной: 8, 9, 11, 15, 19, 20, 21, 7, 3, 2, 1, 5, 6, 4, 13, 14, 10, 12, 17, 16, 18. Результат работы программы следующий:
Рис.3. Результат работы приложения
Замечание. Идеально сбалансированные деревья изобретены для сокращения времени работы вычислительных алгоритмов, связанных с необходимостью частого прохода по ветвям дерева (напомним, что ветвь - это путь от корня дерева до листа). Одним из примеров подобного рода алгоритмов является поиск информации в дереве. В случае, если дерево является идеально сбалансированным, поиск осуществляется так же быстро, как и при дихотомии, то есть для поиска придется перебрать не более log2n вершин, где n - число вершин в дереве.
Одно "но": при формировании идеально сбалансированного дерева ключи необходимо вводить в отсортированном по возрастанию (по убыванию) виде. В этом случае можно построить достаточно простой алгоритм поиска в идеально сбалансированном дереве вершины с заданным ключом.
3. Откомпилируйте и запустите предложенную программу, иллюстрирующую построение дерева Фибоначчи.
#include <iostream.h> struct Node{ int Key; Node* Left; Node* Right;}; class Tree{ private: Node* Root; //Указатель на корень дерева. public: Tree() { Root = NULL; }; void PrintTree (Node*, int); void FibonTree1 (int, Node**); void FibonTree2 (Node**,int *); Node** GetTree() {return &Root;}; Node* GetTree1() {return Root;};}; // ------------ РЕАЛИЗАЦИЯ МЕТОДОВ КЛАССА ---------- void Tree::PrintTree (Node* W, int l){ int i; if (W!=NULL) { PrintTree (W->Right,l+1); for (i=1;i<=l;i++) cout << " "; cout << W->Key << endl; PrintTree (W->Left,l+1); }} void Tree::FibonTree1 (int k, Node** T)// Построение дерева Фибоначчи порядка k с незаполненными// полями Key узлов.{ if (k==0) (*T) = NULL; else if (k==1) { (*T) = new (Node); (*T)->Left = (*T)->Right = NULL; } else { (*T) = new (Node); FibonTree1 (k-1,&((*T)->Left)); FibonTree1 (k-2,&((*T)->Right)); }} void Tree::FibonTree2 (Node** T,int* i)// Заполнение поля Key узлов дерева Фибоначчи.{ if ((*T)!=NULL) { FibonTree2 (&((*T)->Left),i); (*T)->Key = (*i); (*i)++; FibonTree2 (&((*T)->Right),i); }} void main(){ Tree A; int k; cout << "Вводите k..."; cin >> k; int i = 1; // Инициализация самого левого ключа дерева. A.FibonTree1 (k,A.GetTree()); A.FibonTree2 (A.GetTree(),&i); A.PrintTree (A.GetTree1(),0); }
Результат работы программы изображен на рисунке:
Рис. Результат работы приложения
4. Откомпилируйте и запустите предложенную программу, иллюстрирующую показатели баланса дерева Фибоначчи.
#include <iostream.h> struct Node{ int Key; float Bal; //Корневой баланс. Node* Left; Node* Right;}; class Tree{ private: Node* Root; //Указатель на корень дерева. float BalMin; //Баланс дерева Фибоначчи. public: Tree() { Root = NULL; BalMin = 1;}; void PrintTreeBal (Node*, int); void FibonTree1 (int, Node**); void FibonTree2 (Node**,int *); int NodeCount (Node*); Node** GetTree() {return &Root;}; Node* GetTree1() {return Root;}; int GetBalMin() {return BalMin;};}; // ------------ РЕАЛИЗАЦИЯ МЕТОДОВ КЛАССА ---------- void Tree::PrintTreeBal (Node* W, int l)// Вывод бинаpного деpева на экpан дисплея с указанием// показателей баланса весов для каждого узла деpева.{ int i; if (W!=NULL) { PrintTreeBal (W->Right,l+1); for (i=1;i<=l;i++) cout << " "; W->Bal = (float)(NodeCount (W->Left)+1)/(float)(NodeCount (W)+1); if (BalMin > W->Bal) BalMin = W->Bal; cout << W->Key << '('<< W->Bal << ')' << endl; PrintTreeBal (W->Left,l+1); }} void Tree::FibonTree1 (int k, Node** T)// Построение дерева Фибоначчи порядка k с незаполненными// полями Key узлов.{ if (k==0) (*T) = NULL; else if (k==1) { (*T) = new (Node); (*T)->Left = (*T)->Right = NULL; } else { (*T) = new (Node); FibonTree1 (k-1,&((*T)->Left)); FibonTree1 (k-2,&((*T)->Right)); }} void Tree::FibonTree2 (Node** T,int* i)// Заполнение поля Key узлов дерева Фибоначчи.{ if ((*T)!=NULL) { FibonTree2 (&((*T)->Left),i); (*T)->Key = (*i); (*i)++; FibonTree2 (&((*T)->Right),i); }} int Tree::NodeCount (Node* T)// Подсчет количества узлов в бинаpном деpеве T.{ if (T==NULL) return 0; else if (T->Left==NULL && T->Right==NULL) return 1; else return NodeCount(T->Right)+NodeCount(T->Left)+1;} void main(){ Tree A; int k; cout << "Вводите k..."; cin >> k; //Построение дерева Фибоначчи. int i = 1; // Инициализация самого левого ключа дерева. A.FibonTree1 (k,A.GetTree()); A.FibonTree2 (A.GetTree(),&i); //Вывод дерева Фибоначчи, корневых балансов и баланса дерева. A.PrintTreeBal (A.GetTree1(),0); cout << "\nБаланс дерева Фибоначчи: " << A.GetBalMin();}