1.Запустите IDE Borland C++ 5.02. Подготовьте запуск исполнимых файлов в консольном режиме.
2.Откомпилируйте программу по созданию и вывода на экран дерева отрезков. Измените в потоковых операторах вывода текст на русском языке на транслит или на английский язык.
Примечание:Деpево отpезков (впеpвые введенное Дж.Бентли в 1977 г.) - это стpуктуpа данных, созданная для работы с такими интервалами на числовой оси, концы которых принадлежат фиксированному множеству из N абсцисс. Можно считать эти абсциссы целыми числами в интервале [1,N].
Деpево отpезков - это двоичное деpево с коpнем. Для заданных целых чисел l и r таких, что l<r, деpево отpезков T(l,r) стpоится pекуpсивно следующим обpазом: оно состоит из коpня v с паpаметpами B[v]=l и E[v]=r (B и E мнемонически соответствуют словам "Beginning" (начало) и "End" (конец), а если r-l>1, то оно состоит из левого поддеpева T(l,(B[v]+E[v]) DIV 2) и пpавого поддеpева T((B[v]+E[v]) DIV 2),r). Паpаметpы B[v] и E[v] обозначают интеpвал [B[v],E[v]], включенный в [l,r], связанный с узлом v.
Пример Дерева отрезков Интеpвалы, пpинадлежащие множеству:
{ [B[v],E[v]]: v - узел T(l,r) },называются стандаpтными интеpвалами деpева T(l,r).Стандаpтные интеpвалы, пpинадлежащие листьям T(l,r), называются элементаpными интеpвалами. Интервал, связанный с v, это полуоткpытый интеpвал [B[v],E[v]), за исключением узлов самого правого пути в T(l,r), чьи интеpвалы замкнуты.
Можно убедиться, что T(l,r) идеально сбалансиpовано (все его листья пpинадлежат двум смежным уpовням) и имеет глубину [log2(r-l)].
#include <iostream.h>struct node{ int KeyMin; // Минимальный ключ вершины. int KeyMax; // Максимальный ключ вершины. node *Left; // Указатель на "левого" сына. node *Right; // Указатель на "правого" сына.}; class TREE{ private: node *Tree; //Указатель на корень дерева. void Search (int,int,node**); public: TREE() {Tree = NULL;} void BuildTree (); //Построение дерева отрезков. node** GetTree () {return &Tree;} //Получение вершины дерева. void CleanTree (node **); void Vyvod (node **,int);}; void main (){ TREE A; A.BuildTree (); cout<<"\nВывод дерева:\n"; A.Vyvod (A.GetTree(),0); A.CleanTree (A.GetTree());} void TREE::BuildTree ()// Построение бинарного дерева (рекурсивный алгоритм).// Tree - указатель на корень дерева.{ int k1,k2; cout<<"Введите два целых числа...\n"; cin>>k1; cin>>k2; Search (k1,k2,&Tree);} void TREE::Search (int k1, int k2, node **p)// Постpоение деpева отpезков p.// p - указатель на корень дерева.{ if (k2-k1>1) { *p = new (node); (**p).KeyMin = k1; (**p).KeyMax = k2; (**p).Left = (**p).Right = NULL; Search (k1,(k1+k2)/2,&((**p).Left)); Search ((k1+k2)/2,k2,&((**p).Right)); } else { *p = new (node); (**p).KeyMin = k1; (**p).KeyMax = k2; (**p).Left = (**p).Right = NULL; }}void TREE::CleanTree (node **w)//Очистка дерева.//*w - указатель на корень дерева.{ if (*w!=NULL) { CleanTree (&((**w).Left)); CleanTree (&((**w).Right)); delete *w; }}void TREE::Vyvod (node **w,int l)//Изображение дерева *w на экране дисплея (рекурсивный алгоритм).//*w - указатель на корень дерева.{ int i; if (*w!=NULL) { Vyvod (&((**w).Right),l+1); for (i=1; i<=l; i++) cout<<" "; cout<<(**w).KeyMin<<", "<<(**w).KeyMax<<endl; Vyvod (&((**w).Left),l+1); }}Дерево отрезков T(l,r) предназначено для динамического запоминания тех интервалов, чьи концы принадлежат множеству {l, l+1,..., r}.
Дерево отрезков - чрезвычайно гибкая стpуктуpа данных в связи с многочисленными приложениями. Отметим только, что если надо знать число интервалов, содержащих данную точку X, то простой двоичный поиск в T (т.е. прохождение пути от корня к листу) полностью решает эту задачу
3. Откомпилируйте программу работы подсчета числа интервалов, которым принадлежит заданная точка. Проверьте ее работу.
#include <iostream.h>struct node{ int KeyMin; // Минимальный ключ вершины. int KeyMax; // Максимальный ключ вершины. node *Left; // Указатель на "левого" сына. node *Right; // Указатель на "правого" сына.}; class TREE{ private: node *Tree; //Указатель на корень дерева. int S; //Количество вхождений заданной точки в дерево. void Search (int,int,node**); public: TREE() {Tree = NULL; S = 0;} void BuildTree (); //Построение дерева отрезков. node** GetTree () {return &Tree;} //Получение вершины дерева. void CleanTree (node **); void Vyvod (node **,int); int GetCount() { return S;} void Count (node **,float);}; void main (){ TREE A; float X; A.BuildTree (); cout<<"\nВывод дерева:\n"; A.Vyvod (A.GetTree(),0); cout << "\nВведите абсциссу точки: "; cin >> X; A.Count(A.GetTree(),X); cout << "Точка принадлежит "<< A.GetCount() <<" интервалам"; A.CleanTree (A.GetTree());} void TREE::BuildTree ()// Построение бинарного дерева (рекурсивный алгоритм).// Tree - указатель на корень дерева.{ int k1,k2; cout<<"Введите два целых числа...\n"; cin>>k1; cin>>k2; Search (k1,k2,&Tree);}void TREE::Search (int k1, int k2, node **p)// Постpоение деpева отpезков p. p - указатель на корень дерева.{ if (k2-k1>1) { *p = new (node); (**p).KeyMin = k1; (**p).KeyMax = k2; (**p).Left = (**p).Right = NULL; Search (k1,(k1+k2)/2,&((**p).Left)); Search ((k1+k2)/2,k2,&((**p).Right)); } else { *p = new (node); (**p).KeyMin = k1; (**p).KeyMax = k2; (**p).Left = (**p).Right = NULL; }}void TREE::Count (node **p, float X)// Подсчет количества интеpвалов деpева p, содеpжащих точку X.{ if (*p!=NULL) { Count (&((**p).Right),X); if (X>=(**p).KeyMin && X<=(**p).KeyMax) S++; Count (&((**p).Left),X); }}void TREE::CleanTree (node **w)//Очистка дерева. *w - указатель на корень дерева.{ if (*w!=NULL) { CleanTree (&((**w).Left)); CleanTree (&((**w).Right)); delete *w; }}void TREE::Vyvod (node **w,int l)//Изображение дерева *w на экране дисплея (рекурсивный алгоритм).//*w - указатель на корень дерева.{ int i; if (*w!=NULL) { Vyvod (&((**w).Right),l+1); for (i=1; i<=l; i++) cout<<" "; cout<<(**w).KeyMin<<", "<<(**w).KeyMax<<endl; Vyvod (&((**w).Left),l+1); }}
4. Откомпилируйте программу по созданию бинарного дерева поиска, программа демонстрирует разнообразные его обходы, вывод дерева и определение его высоты, а также производит "очистку" дерева (рекурсивные алгоритмы). Проверьте работу программы, введите исходные данные для построения различных деревьев.
#include<iostream.h>struct node{ int Key; int Count; node *Left; node *Right;}; class TREE{ private: node *Tree; //Указатель на корень дерева. void Search (int,node**); public: TREE() {Tree=NULL;} node** GetTree () {return &Tree;} //Получение вершины дерева. void BuildTree (); void CleanTree (node **); void ObhodEnd (node **); void ObhodLeft (node **); void ObhodBack (node **); void Vyvod (node**,int); int Height (node**);}; void main (){ TREE A; A.BuildTree (); cout<<"\nВывод дерева:\n"; A.Vyvod (A.GetTree(),0); cout<<"\nВысота дерева:"<<A.Height(A.GetTree())<<endl; cout<<"\nЛевосторонний обход дерева: "; A.ObhodLeft (A.GetTree()); cout<<"\nКонцевой обход дерева: "; A.ObhodEnd (A.GetTree()); cout<<"\nОбратный обход дерева: "; A.ObhodBack (A.GetTree()); A.CleanTree (A.GetTree());} void TREE::BuildTree ()// Построение бинарного дерева (рекурсивный алгоритм).// Tree - указатель на корень дерева.{ int el; cout<<"Вводите ключи вершин дерева...\n"; cin>>el; while (el!=0) { Search (el,&Tree); cin>>el; }} void TREE::Search (int x,node **p)// Поиск вершины с ключом x в дереве со вставкой// (рекурсивный алгоритм).// *p - указатель на корень дерева.{ if (*p==NULL) {// Вершины в дереве нет; включить ее. *p = new(node); (**p).Key = x; (**p).Count = 1; (**p).Left = NULL; (**p).Right = NULL; } else if (x<(**p).Key) Search (x,&((**p).Left)); else if (x>(**p).Key) Search (x,&((**p).Right)); else (**p).Count = (**p).Count + 1;} void TREE::ObhodLeft (node **w)//Левосторонний обход дерева.//*w - указатель на корень дерева.{ if (*w!=NULL) { cout<<(**w).Key<<" "; ObhodLeft (&((**w).Left)); ObhodLeft (&((**w).Right)); }} void TREE::ObhodEnd (node **w)//Концевой обход дерева.//*w - указатель на корень дерева.{ if (*w!=NULL) { ObhodEnd (&((**w).Left)); ObhodEnd (&((**w).Right)); cout<<(**w).Key<<" "; }} void TREE::ObhodBack (node **w)//Обратный обход дерева.//*w - указатель на корень дерева.{ if (*w!=NULL) { ObhodBack (&((**w).Left)); cout<<(**w).Key<<" "; ObhodBack (&((**w).Right)); }} void TREE::CleanTree (node **w)//Очистка дерева.//*w - указатель на корень дерева.{ if (*w!=NULL) { CleanTree (&((**w).Left)); CleanTree (&((**w).Right)); delete *w; }} void TREE::Vyvod (node **w,int l)//Изображение дерева *w на экране дисплея// (рекурсивный алгоритм).//*w - указатель на корень дерева.{ int i; if (*w!=NULL) { Vyvod (&((**w).Right),l+1); for (i=1; i<=l; i++) cout<<" "; cout<<(**w).Key<<endl; Vyvod (&((**w).Left),l+1); }} int TREE::Height (node **w)//Определение высоты бинарного дерева.//*w - указатель на корень дерева.{ int h1,h2; if (*w==NULL) return (-1); else { h1 = Height (&((**w).Left)); h2 = Height (&((**w).Right)); if (h1>h2) return (1 + h1); else return (1 + h2); }}
.