2. Бинарное дерево поиска.
Дерево поиска – это двоичное дерево, в котором выполняются следующие условия
а) l(u) < l(v) для всех вершин u, v, если вершина u находится в поддереве, корень которого – левый преемник v;
б) l(u) > l(v) для всех вершин u, v, если вершина u находится в поддереве, корень которого – правый преемник v;
в) для всякого значения aÎ S существует единственная вершина v, для которой l(v) = a
Реализация программы
struct elem
{
char s[50];
int size;
public:
bool operator>(info d)
{ return (strcmp(s, d.s) == 1);}
};
struct tree
{
elem el;
tree *left;
tree *right;};
//добавление элемента в бинарное дерево поиска по ключу - строка
void IncludeString(tree **t,info w)
{
tree *q,*r,*z=NULL;
if (!(*t))
{
*t = new tree;
(*t)->el =w;
(*t)->left = NULL;
(*t)->right = NULL;
}
else
{
q = *t;
while (q)
{
z = q;
if (q->el>w)
q = q->left;
else
q = q->right;
}
r = new tree;
r->el = w;
r->left = NULL;
r->right = NULL;
if (z->el>w)
z->left = r;
else
z->right = r;
}
}
//добавление элемента в бинарное дерево поиска по ключу - размер
void IncludeSize(tree **t, elem w)
{
tree *q, *r, *z=NULL;
if (!(*t))
{
*t = new tree;
(*t)->el = w;
(*t)->left = NULL;
(*t)->right = NULL;
}
else
{
q = *t;
while (q)
{
z = q;
if (q->el.size>w.size)
q = q->left;
else
q = q->right;
}
r = new tree;
r->el = w;
r->left = NULL;
r->right = NULL;
if (z->el.size>w.size)
z->left = r;
else
z->right = r;
}
}
//поиск данного элемента по строке в бинарном дереве поиска
void search_elem_String(tree *t, elem w)
{
tree *q = t;
while (q)
{
if (w > q->el)
q = q->right;
else
if (q->el > w)
q = q->left;
else
return;
}
}
//поиск данного элемента по размеру в бинарном дереве поиска
void search_elem_size(tree *t, elem w)
{
tree *q = t;
while (q)
{
if (w.size > q->el.size)
q = q->right;
else
if (q->el.size > w.size)
q = q->left;
else
{
q = q->right;
}
}
}
//поиск максимального элемента в бинарном дереве поиска
info search_max(tree *t)
{
tree *q = t;
while (q->right)
{
q = q->right;
}
return q->el;
}
//поиск минимального элемента в бинарном дереве поиска
info search_min(tree *t)
{
tree *q = t;
while (q->left)
{
q = q->left;
}
return q->el;
}
//поиск высоты бинарного дерева поиска
void heightTree(tree *t,int i)
int max=0;
if (t != NULL)
{
if (i > max) max = i;
heightTree(t->left, ++i);
i--;
heightTree(t->right, ++i);
i--;
}
}
//сортировка
void sort(tree *t, FILE *in)
{ if (t)
{
sort(t->left,in);
fprintf(in, "%ld\n", t->el.size);
sort(t->right, in);
}
}
Результаты.
|
Ключ |
Высота |
Кол-во узлов |
Мин. элемент |
Макс. элемент |
Время на построение |
Время на сортировку |
|
Имя |
1640 |
128200 |
Имя:taz.bmp Размер: 1438
|
Имя: Онлайн-регистрация продукта ASUS.lnk Размер : 1142
|
12009 |
240 |
|
Размер |
3430 |
128200 |
Имя:lol.txt Размер: 0 |
Имя : hiberfil.sys Размер: 6775930880 |
2124 |
242 |
Поиск элемента по размеру
Среднего: 1343 Худшего: 3543
Поиск элемента ключ- имя файла
Среднего: 812 Худшего: 1543