Похожие презентации:
Деревья. Обход всего дерева. (Лекция 2)
1.
Обход всего дерева2.
void wrtree(ttree *p){
if (p==NULL) return;
wrtree(p->left);
cout << p->inf << " ";
wrtree(p->rigth);
}
3.
Поиск элемента с заданным ключем4.
void 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);
}
5.
else{
b=true;
inf=p->inf;
}
}
return;
}
6.
Поиск элемента с максимальным ключем7.
int 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;
}
9.
Удаление всего дерева10.
ttree *deltree(ttree *p){
if (p==NULL) return NULL;
deltree(p->left);
deltree(p->rigth);
delete(p);
return NULL;
}
11.
Удаление элемента с заданным ключем12.
Удаление листа с ключом key:5
pr
5
ps
key=4
8
4
N
N
N
8
13.
Удаление узла имеющего одну дочь:pr
5
key=6 6
7
5
ps
7
N
14.
Удаление узла, имеющего двух дочерей1
5
key=7
v
7
pr
1
5
ps
4
6
9
4
9
w
2
6
5
8
N
1
0
2
5
8
10
15.
ttree *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;
}
25.
if (pr->left == ps) // Если удаляемый узел слеваpr->left = w;
else
// Если удаляемый узел справа
pr->rigth = w;
delete(ps);
return proot;
}