Деревья. Обход всего дерева. (Лекция 2)

Содержание

Слайд 2

void wrtree(ttree *p)
{
if (p==NULL) return;
wrtree(p->left);
cout << p->inf <<

void wrtree(ttree *p) { if (p==NULL) return; wrtree(p->left); cout inf wrtree(p->rigth); }
" ";
wrtree(p->rigth);
}

Слайд 3

Поиск элемента с заданным ключем

Поиск элемента с заданным ключем

Слайд 4

void poisktree(ttree *p,int key,
bool &b, int &inf)
{
if ((p

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;
}

else { b=true; inf=p->inf; } } return; }

Слайд 6

Поиск элемента с максимальным ключем

Поиск элемента с максимальным ключем

Слайд 7

int poiskmaxtree(ttree *p)
{
while (p->rigth != NULL) p = p->rigth;
return p->inf;
}

int poiskmaxtree(ttree *p) { while (p->rigth != NULL) p = p->rigth; return p->inf; }

Слайд 8

Поиск элемента с минимальным ключем

int poiskmintree(ttree *p)
{
while (p->left != NULL) p

Поиск элемента с минимальным ключем int poiskmintree(ttree *p) { while (p->left !=
= p-> left;
return p->inf;
}

Слайд 9

Удаление всего дерева

Удаление всего дерева

Слайд 10

ttree *deltree(ttree *p)
{
if (p==NULL) return NULL;
deltree(p->left);
deltree(p->rigth);
delete(p);

ttree *deltree(ttree *p) { if (p==NULL) return NULL; deltree(p->left); deltree(p->rigth); delete(p); return NULL; }

return NULL;
}

Слайд 11

Удаление элемента с заданным ключем

Удаление элемента с заданным ключем

Слайд 12

Удаление листа с ключом key:

8

5

8

N

N

N

pr

4

5

key=4

ps

Удаление листа с ключом key: 8 5 8 N N N pr 4 5 key=4 ps

Слайд 13

Удаление узла имеющего одну дочь:

N

5

7

6

pr

key=6

ps

5

7

Удаление узла имеющего одну дочь: 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

Удаление узла, имеющего двух дочерей 4 2 6 8 10 ps w

Слайд 15

ttree *dellist(ttree *proot, int inf)
{
ttree *ps = proot, *pr = proot,

ttree *dellist(ttree *proot, int inf) { ttree *ps = proot, *pr =
*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

// Если узел не имеет дочерей if ((ps->left == NULL) && (ps->rigth
== NULL))
{
if (ps == pr) // Если это был последний элемент
{
delete(ps);
return NULL;
}

Слайд 17

if (pr->left == ps) // Если удаляемый узел слева
pr->left = NULL;
else //

if (pr->left == ps) // Если удаляемый узел слева pr->left = NULL;
Если удаляемый узел спава
pr->rigth = NULL;
delete(ps);
return proot;
}

Слайд 18

// Если узел имеет дочь только справа
if (ps->left == NULL)
{
if

// Если узел имеет дочь только справа if (ps->left == NULL) {
(ps == pr) // Если удаляется корень
{
ps = ps->rigth;
delete(pr);
return ps;
}

Слайд 19

if (pr->left == ps) // Если удаляемый узел слева
pr->left =

if (pr->left == ps) // Если удаляемый узел слева pr->left = ps->rigth;
ps->rigth;
else // Если удаляемый узел спава
pr->rigth = ps->rigth;
delete(ps);
return proot;
}

Слайд 20

// Если узел имеет дочь только слева
if (ps->rigth == NULL)
{
if

// Если узел имеет дочь только слева if (ps->rigth == NULL) {
(ps == pr) // Если удаляется корень
{
ps = ps->left;
delete(pr);
return ps;
}

Слайд 21

if (pr->left == ps) // Если удаляемый узел слева
pr->left = ps->left;
else //

if (pr->left == ps) // Если удаляемый узел слева pr->left = ps->left;
Если удаляемый узел спава
pr->rigth = ps->left;
delete(ps);
return proot;
}

Слайд 22

// Если узел имеет двух дочерей

w = ps->left;
if (w->rigth ==

// Если узел имеет двух дочерей w = ps->left; if (w->rigth ==
NULL) // Если максимасальный
// следует за ps
w->rigth = ps->rigth;

Слайд 23

else // Если максимасальный не следует за ps
{
while (w->rigth

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;
}

if (ps == pr) // Если удаляется корень { delete(ps); return w; }
Имя файла: Деревья.-Обход-всего-дерева.-(Лекция-2).pptx
Количество просмотров: 34
Количество скачиваний: 0