Слайд 2void wrtree(ttree *p)
{
if (p==NULL) return;
wrtree(p->left);
cout << p->inf <<
" ";
wrtree(p->rigth);
}
Слайд 3Поиск элемента с заданным ключем
Слайд 4void poisktree(ttree *p,int key,
bool &b, int &inf)
{
if ((p
!= NULL) && (b != true))
{
if (p->inf !=key)
{
poisktree(p->left, key, b, inf);
poisktree(p->rigth, key, b, inf);
}
Слайд 5else
{
b=true;
inf=p->inf;
}
}
return;
}
Слайд 6Поиск элемента с максимальным ключем
Слайд 7int poiskmaxtree(ttree *p)
{
while (p->rigth != NULL) p = p->rigth;
return p->inf;
}
Слайд 8Поиск элемента с минимальным ключем
int poiskmintree(ttree *p)
{
while (p->left != NULL) p
= p-> left;
return p->inf;
}
Слайд 10ttree *deltree(ttree *p)
{
if (p==NULL) return NULL;
deltree(p->left);
deltree(p->rigth);
delete(p);
return NULL;
}
Слайд 11Удаление элемента с заданным ключем
Слайд 12Удаление листа с ключом key:
8
5
8
N
N
N
pr
4
5
key=4
ps
Слайд 13Удаление узла имеющего одну дочь:
N
5
7
6
pr
key=6
ps
5
7
Слайд 14Удаление узла, имеющего двух дочерей
4
2
6
8
10
ps
w
N
5
7
15
pr
key=7
v
9
4
2
5
8
10
15
6
9
Слайд 15ttree *dellist(ttree *proot, int inf)
{
ttree *ps = proot, *pr = proot,
*w, *v;
// Поиск удалемого узла
while ((ps != NULL) && (ps->inf != inf))
{
pr = ps;
if (inf < ps->inf) ps = ps->left;
else ps = ps->rigth;
}
if (ps == NULL) return proot; // Если узел не найден
Слайд 16// Если узел не имеет дочерей
if ((ps->left == NULL) &&
(ps->rigth
== NULL))
{
if (ps == pr) // Если это был последний элемент
{
delete(ps);
return NULL;
}
Слайд 17 if (pr->left == ps) // Если удаляемый узел слева
pr->left = NULL;
else //
Если удаляемый узел спава
pr->rigth = NULL;
delete(ps);
return proot;
}
Слайд 18// Если узел имеет дочь только справа
if (ps->left == NULL)
{
if
(ps == pr) // Если удаляется корень
{
ps = ps->rigth;
delete(pr);
return ps;
}
Слайд 19 if (pr->left == ps) // Если удаляемый узел слева
pr->left =
ps->rigth;
else // Если удаляемый узел спава
pr->rigth = ps->rigth;
delete(ps);
return proot;
}
Слайд 20// Если узел имеет дочь только слева
if (ps->rigth == NULL)
{
if
(ps == pr) // Если удаляется корень
{
ps = ps->left;
delete(pr);
return ps;
}
Слайд 21 if (pr->left == ps) // Если удаляемый узел слева
pr->left = ps->left;
else //
Если удаляемый узел спава
pr->rigth = ps->left;
delete(ps);
return proot;
}
Слайд 22// Если узел имеет двух дочерей
w = ps->left;
if (w->rigth ==
NULL) // Если максимасальный
// следует за ps
w->rigth = ps->rigth;
Слайд 23 else // Если максимасальный не следует за ps
{
while (w->rigth
!= NULL)
{
v = w;
w = w->rigth;
}
v->rigth = w->left;
w->left = ps->left;
w->rigth = ps->rigth;
}
Слайд 24 if (ps == pr) // Если удаляется корень
{
delete(ps);
return w;
}