Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Tree part 1

.pdf
Скачиваний:
12
Добавлен:
03.06.2015
Размер:
1.08 Mб
Скачать

Деревья

Tree

Динамические структуры данных на C

1

Tree

Дерево это структура данных, состоящая из узлов и соединяющих их направленных рёбер (дуг), причём

в каждый узел (кроме корневого)

2

 

ведёт ровно одна дуга.

 

И нет циклов. А есть корень.

5

Лист – это узел, из которого не выходит ни одной дуги.

1

1

1

 

 

 

 

 

 

 

2

3

 

2

 

2

3

 

4

5

 

3

 

4

5

 

6

 

 

 

 

корень

1

4

3

8

7

6

9 10

1

2 3

4

дерево

дерево

не дерево

не дерево 2

 

 

Деревья

3

Tree – рекурсивная структура данных

Рекурсивное определение:

1

 

 

 

1. Пустая структура – это дерево.

 

 

2. Дерево – это корень и несколько

2

3

связанных с ним (под)деревьев.

4

 

 

5

Двоичное (бинарное) дерево – это

 

6

дерево, в котором каждый узел имеет не

 

 

более двух сыновей.

1.Пустая структура – это двоичное дерево.

2.Двоичное дерево – это корень и два связанных с ним двоичных дерева (левое и правое поддеревья).

4

Tree

Сын (дочь) узла x – это узел, в который

 

1

 

существует дуга непосредственно из узла

2

 

 

x.

 

3

 

 

 

Родитель (parent, father) узла x – это узел,

 

4

5

из которого существует дуга

 

 

 

 

непосредственно в узел x.

 

 

6

Брат узла x (sibling) – это узел, у которого

 

 

 

тот же родитель, что и у узла x. Предок узла x – это узел, из которого

существует путь по стрелкам в узел x. Потомок узла x – это узел, в который

существует путь по стрелкам из узла x. Высота дерева – это наибольшее

расстояние от корня до листа (количество

дуг).

5

Depth, Level & Height Tree

1

0

1

0 Depth Level

2

3

1 Level

4

5

2

 

 

3 Height

6

6

Применение деревьев

1)поиск данных;

2)сортировка данных;

3)обработка арифметических выражений;

4)кодирование (метод Хаффмана).

7

Полное дерево

число узлов на уровне n =2^k, k=0,1,.. полное число узлов = 2^(h+1)-1

h (height) – высота дерева

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

8

Полное дерево

k

2*k 2*k+1

9

Узловое представление

- несколько массивов

type

data

[n]

 

 

 

int

left

[n]

 

 

 

int

right

[n]

 

 

 

int

parent

[n]

 

 

 

int

brother

[n]

 

 

 

10

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]