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

Обходы дерева

Обход дерева – это способ методичного исследования узлов дерева, при

Обходы деревьев в глубину

Пусть T – дерево, r- корень, v1, v2,…,

Обходы деревьев в глубину. Пример 1.

Прямой Обратный Внутренний

1

2

6

3

7

8

4

5

9

10

10

4

9

3

5

8

1

1

5

6

7

2

2

10

6

3

7

9

8

4

Обходы деревьев в глубину. Пример 2

+ * a – d e

Обход дерева в ширину

- это обход вершин дерева по уровням, начиная

Обход дерева в ширину. Пример

b

h

i

j

k

l

d

e

f

a

g

b

i

h

a

j

k

l

d

e

f

g

Представления деревьев

Определение. Левое скобочное представление дерева Т (обозначается Lrep(Т)) можно получить,

Скобочные представления деревьев

Lrep(T) = b ( h ( a, j (

Представление дерева списком прямых предков

Составляется список прямых предков для вершин дерева

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

Определение. Деревом двоичного поиска для множества S называется помеченное

Дерево двоичного поиска. Пример

Пусть S = {1, 2, 3, 4, 5,

Алгоритм просмотра дерева двоичного поиска

Вход: Дерево T двоичного поиска для множества

Лабораторная работа: построение дерева двоичного поиска

Вход: последовательность слов произвольной длины (либо

Реализация бинарных деревьев на Си

typedef struct node {
char *word;
struct node *left;
struct

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

Теорема.
Среднее число сравнений, необходимых для вставки n случайных элементов

Вставка элемента в сбалансированное дерево

Пусть r – корень, L – левое

Вставка в левое поддерево

A

B

3

2

1

A

B

3

2

1