Деревья. Двоичные (бинарные) деревья

Способы изображения древовидных структур

Граф

Вложенные скобки (A(B(E,F(I,J)),C(G),D(H)))

Вложенные множества

Ломаная последовательность
A
B
E
F
I
J
C
G
D
H

Двоичные (бинарные) деревья

{R} - корневой узел
{L1, L2, ..., Lm} - левое

N глубина = int (log2N).
N=10 000 int(log210 000) = int(13.28) = 13

Структура двоичного дерева

С использованием массива TREE[n]; TREE[K] - TREE[2K+1], TREE[2K+2]
В виде динамической структуры
struct

Идеально сбалансированное дерево

Взять один узел в качестве корня.
Левое поддерево: nl=n/2.
Правое поддерево:

TREE* maketree(int n)
{TREE *ptr;
int nl, nr, x;
if (n==0) return NULL;
nl=n/2;
nr=n-nl-1;
ptr=new (TREE);
cout

Двоичные деревья выражений

6*(4-2)

(3+5)*(8-4)+2

(7/3+(5+6)*2)/4

Деревья двоичного поиска

O(N) O(log2N)

Пример: 32, 1, 98, -4, 34, -87, 25, 6, 10, 9,

void build(TREE *tt, char ch)
{
if (chdann)
if (tt->pleft==NULL)
{left=new TREE;
tt->pleft=left;

Операции с двоичными деревьями

Алгоритмы поиска
TREE * poisk(TREE *ptr, char ch)
{
while(ptr->dann!=ch

TREE *parent=NULL; TREE *find(char x, TREE* ptr) { while (ptr!=NULL) { if (x==ptr->dann) break; else

Алгоритмы обхода дерева

Прямой
void preorder(TREE *ptr)
{
if (ptr) {
putchar(ptr->dann);
if (ptr->pleft) preorder(ptr->pleft);
if (ptr->pright) preorder(ptr->pright);
}
}

10

5

-7

0

6

8

18

29

Симметричный
void inorder(TREE *ptr)
{
if (ptr) {
if (ptr->pleft) inorder(ptr->pleft);
putchar(ptr->dann);
if (ptr->pright) inorder(ptr->pright);
}
}

-7

0

5

6

8

10

18

29

Обратный
void postorder(TREE *ptr)
{
if (ptr) {
if (ptr->pleft) postorder(ptr->pleft);
if (ptr->pright) postorder(ptr->pright);
putchar(ptr->dann);
}
}

0

-7

8

6

5

29

18

10

Вертикальная печать дерева

A

B

C

D

E

F

G

H

Удаление дерева

TREE* del(TREE *t)
{
if (t!=NULL)
{
del(t->pleft);
del(t->pright);
delete t;
}
return NULL;
}
root=del(root);

3

2

7

0

5

9

4

6

11

Удаление элемента из дерева

Элемента со значением, равным х, в дереве не

Элемент со значением х имеет двух потомков.

3

2

7

0

5

9

4

6

11

D
P
R
PR

R->right=D->right;
P->left=R;

A

Б

Г

В

Д

D

=PR

R

P

PR->right=R->left;

A

Б

Г

В

Д

D

PR

R

P

E

Ж

З

К

И

Л

Двоичные деревья, представляемые массивами

A[i]
Индекс левого наследника = 2*i+1.
Индекс правого наследника

int A[]={5, 1, 3, 9, 6, 4, #, 7, #, #,

Турнирная сортировка

A[8]={85, 20, 15, -45, 10, 41, 10, 36}
2k≥N
k=3

O(n log2n)

Пирамиды (heap-tree)

Максимальные Минимальные

Преобразование массива в пирамиду

n n-1 (n-2)/2

Пример: Построим максимальную пирамиду
int H[10]={7, 12, 72, 43,

H[4]=9
H[9]=86
H[3]=43
H[8]=72 H[7]=30
H[2]=72
H[5]=47 H[6]=18
H[1]=12
H[3]=72 H[4]=86
H[0]=7
H[1]=86 H[2]=72

7

12

72

43

9

47

18

30

86

72

Добавление элемента в пирамиду

86

72

72

43

12

47

18

30

9

7

80

Удаление из пирамиды

86

80

72

43

72

47

18

30

9

7

12

Пирамидальная сортировка

Пример: int A[]={54, 21, 90, 38, 23, 0};

54

21

90

38

23

0

0

21

23

38

n log2n