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

Наряду со стандартными рассмотренными ранее способами представления деревьев существуют и другие способы его задания корневых деревьев. Способы его задания корневых деревьев рассмотрим на следующем примере:

A

B C D

E F G H I

1) с помощью вложенных скобок (согласно определению корневого дерева):

{A{B{E, F}{C{G}{D{H, I}}

Вложенные скобки применяются при грамматическом разборе арифметических выражений.

2) в виде уступчатого списка:

A Уступчатый список применяется для представления

вложенных элементов данных (структуры.

B

E

F

C

E

D

H

I

3) в виде десятичной системы Дьюи:

1. A Применяется в библиографии.

1.1. B

1.1.1. E

1.1.2. F

1.2. C

1.2.1. G

1.3. D

1.3.1. H

1.3.2. I

4) в виде системы множеств:

A C

B G D

E F H I

Применяется для задания структуры областей идентификаторов.

Обобщением понятия корневого дерева является понятие корневого леса. Под лесом понимается упорядоченное множество непересекающихся корневых деревьев. Отражением близости этих понятий является простота преобразования дерева в лес и, наоборот. Исключение корня превращает дерево в лес, а добавление одной вершины (корня) превращает лес в дерево.

Рассмотрим пример упорядоченных деревьев.

1 1 1

2 3 2 3 2

4 5 6 4 5 6 3 4 5

7 8 7 8 6 7 8

Как упорядоченные деревья они все различны:

T1={1{2{4, 5, 6{7, 8}}, 3}}

T2={1{2}{3{4, 5{7, 8}, 6}}

T3{1{2{3{6, 7}, 4, 5{8}}

Как свободные деревья они все изоморфны. Последнее дерево получаем, когда в качестве корня берем пятую вершину первого дерева.

Корневые деревья можно использовать при решении задач принятия решений.

Каждому листу в таком дереве поставлено в соответствие некоторое решение из конечного множества известных решений, а каждой вершин – проверка некоторого условия, определяющего направление нашего движения по дереву.

В каждой внутренней вершине мы проверяем условие и двигаемся по дереву, пока не попадем в вершину, являющуюся листом – что и будет нашим решением.

Пример

Есть 8 монет, среди них одна фальшивая. Ее надо найти за минимальное число взвешиваний на балансовых весах.

1, 2, 3, 4, 5, 6, 7, 8

1, 2, 3 и 4, 5, 6

< = >

1 и 2 7 и 8 4 и 5

< = > < = > < = >

1 3 2 7 x 8 4 6 5