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

1. Деревья

Дерево
Корень дерева
Листья
Пустое дерево
Предки, потомки
Уровень узла
Глубина дерева
Уровень 0
А
Уровень 1
В
С
D
Уровень 2
E
F
G
H
Уровень 3
I
J

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

• Граф
А
В
С
E
F
I
D
G
J
• Вложенные скобки
(A(B(E,F(I,J)),C(G),D(H)))
H

3.

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

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

{R} - корневой узел
{L1, L2, ..., Lm} - левое поддерево R
{R1, R2, ..., Rm} - правое поддерево R
R
n
1 … 2n
R1
L1
L2
R2
L3
L4
Левое поддерево
Правое
поддерево

5.

Вырожденное дерево
(глубина 4)
N
глубина = int (log2N).
N=10 000
int(log210 000) = int(13.28) = 13
Законченное дерево
(Глубина 3)
Полное дерево
(Глубина 2)

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

• С использованием массива
TREE[n];
TREE[K] - TREE[2K+1], TREE[2K+2]
• В виде динамической структуры
struct TREE{
int dann;
TREE *pleft;
left
A
right
TREE *pright;
};
left
B
right
NULL
NULL
D
NULL
NULL
G
left
NULL
E
C
right
NULL
right
NULL
H
NULL
F
NULL

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

Взять один узел в качестве корня.
Левое поддерево: nl=n/2.
Правое поддерево: nr=n-nl-1.
Пример: 6, 4, 2, 3, 8, 9, 0, 1, 7
6
4
2
3
9
8
0
1
7

8.

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 << "Input ";
cin >> ptr->dann;
ptr->pleft=maketree(nl);
ptr->pright=maketree(nr);
return ptr;
}
TREE *root;
root=maketree(n);
void print(TREE *ptr, int h)
{
if (ptr) {
print(ptr->pright,h+1);
for (int i=1;i<=h;i++) cout << " ";
cout << ptr->dann << endl;
print(ptr->pleft,h+1);
}
}

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

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

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

7
5
2
-3
5
18
10
90
6
0
6
O(N)
-7
O(log2N)
8
9

11.

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

12.

void build(TREE *tt, char ch)
{
if (ch<tt->dann)
if (tt->pleft==NULL)
{left=new TREE;
tt->pleft=left;
left->dann=ch;
left->pleft=NULL;
left->pright=NULL;
}
else build(tt->pleft,ch);
else
if (tt->pright==NULL)
{right=new TREE;
tt->pright=right;
right->dann=ch;
right->pleft=NULL;
right->pright=NULL;
}
else build(tt->pright,ch);
}
root=new TREE;
root->dann=str[0];
root->pright=NULL;
root->pleft=NULL;
for (int i=1; i<strlen(str); i++)
build(root,*(str+i));

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

Алгоритмы поиска
TREE * poisk(TREE *ptr, char ch)
{
while(ptr->dann!=ch && ptr)
if (ch<ptr->dann) ptr=ptr->pleft;
else ptr=ptr->pright;
return ptr;
}
10
ptr
5
2
-3
18
10
6
90

14. TREE *parent=NULL; TREE *find(char x, TREE* ptr) { while (ptr!=NULL) { if (x==ptr->dann) break; else {parent=ptr; if (x<ptr->dann) ptr=ptr->pleft; else ptr=ptr->pright; } } return ptr; }

TREE * poisk(TREE *ptr,
char ch,)
{
if (ch<ptr->dann)
ptr=poisk(ptr->pleft, ch);
if (ch>ptr->dann)
ptr=poisk(ptr->pright, ch);
else return ptr;
}
TREE *parent=NULL;
TREE *find(char x, TREE* ptr)
{
while (ptr!=NULL)
{ if (x==ptr->dann)
break;
else
{parent=ptr;
if (x<ptr->dann)
ptr=ptr->pleft;
else ptr=ptr->pright;
}
}
return ptr;
}

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

• Прямой
void preorder(TREE *ptr)
{
if (ptr) {
putchar(ptr->dann);
if (ptr->pleft) preorder(ptr->pleft);
if (ptr->pright) preorder(ptr>pright);
}
}
ptr
5
-7
10
5 -7
0 6
8 18 29
10
18
6
0
29
8

16.

• Симметричный
void inorder(TREE *ptr)
{
if (ptr) {
if (ptr->pleft) inorder(ptr->pleft);
putchar(ptr->dann);
if (ptr->pright) inorder(ptr->pright);
}
}
ptr
5
-7
-7 0 5 6 8
10 18 29
10
18
6
0
29
8

17.

• Обратный
void postorder(TREE *ptr)
{
if (ptr) {
if (ptr->pleft) postorder(ptr->pleft);
if (ptr->pright) postorder(ptr->pright);
putchar(ptr->dann);
}
}
ptr
10
5
-7
0
-7
8 6 5 29
18 10
18
6
0
29
8

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

A
А
В
D
B
C
C
D
E
D
E
F
E
F
G
F
G
H
G
H
С
E
F
G
H
A B C D E F G H
H
G

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

TREE* del(TREE *t)
{
if (t!=NULL)
{
del(t->pleft);
del(t->pright);
delete t;
}
return NULL;
}
root=del(root);
ptr
3
2
7
0
5
4
9
6
11

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

Элемента со значением, равным х, в дереве не
существует;
Элемент со значением х является терминальным
узлом;
Элемент со значением х имеет одного потомка;
3
2
3
7
0
5
4
2
9
6
7
0
11
5
4
9
6
11

21.

• Элемент со значением х имеет двух потомков.
3
2
D
P
R
PR
7
0
5
4
9
6
11

22.

A
Б
R
D =PR
В
Д
R->right=D->right;
P->left=R;
P
Г

23.

A
Б
В
D
Г
Д
З
P
E
PR Ж
К
И
Л
R
PR->right=R->left;

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

A[i]
Индекс левого наследника = 2*i+1.
Индекс правого наследника = 2*i+2.
Индекс родителя = (i-1)/2.
Пример:
int A[]={5, 1, 3, 9, 6, 2, 4, 7, 0, 8};
5
1
3
9
7
6
0
8
2
4

25.

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

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

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

27.

-45
10
-45
85
-45
20
15
-45
10
10
-45
20
10
41
10
36

28.

10
15
10
20
85
-45
15
20
10
15
10
#
10
10
41
10
36

29.

85
85
85
85
-45
#
10
#
10
#
15
#
#
#
20
36
41
O(n log2n)
#

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

Максимальные
Минимальные
60
3
20
18
-9
32
10
0
12
7
9
11
25
50
20
12
70
55

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

n
n-1
(n-2)/2
Пример: Построим максимальную пирамиду
int H[10]={7, 12, 72, 43, 9, 47, 18, 30, 72, 86}
5, 6, …, 9
4, 3, …, 0
7
12
72
43
30
9
72
86
47
18

32.

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

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

86
72
72
43
30
12
7
9
47
80
18

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

86
80
72
43
30
72
7
9
47
12
18

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

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

36. Сбалансированные деревья

AVL
struct AVLTREE{
int dann;
int balance;
AVLTREE *pleft;
AVLTREE *pright;
};
balance<0
balance=0
balance>0