![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Способы представления корневых деревьев
Наряду со стандартными рассмотренными ранее способами представления деревьев существуют и другие способы его задания корневых деревьев. Способы его задания корневых деревьев рассмотрим на следующем примере: A
E F G H I
1) с помощью вложенных скобок (согласно определению корневого дерева): {A{B{E, F}{C{G}{D{H, I}} Вложенные скобки применяются при грамматическом разборе арифметических выражений.
2) в виде уступчатого списка:
вложенных элементов данных (структуры. 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
|