и специального символа сделаем следующий

Относительно функтора и специального символа сделаем следующий выбор:

Пусть атом nil представляет пустое дерево.

В качестве функтора примем дер, так что дерево с корнем X, левым поддеревом L

и правым поддеревом R будет иметь вид терма дер( L, X, R) (см. рис. 9.5).

В этом представлении дерево рис. 9.4 выглядит как

        дер( дер( nil, b, nil), a,

                    дер( дер( nil, d, nil), с, nil) ).

Теперь рассмотрим отношение принадлежности, которое будем обозначать внутри. Цель

        внутри( X, Т)

истинна, если Х есть вершина дерева Т. Отношение внутри можно определить при помощи следующих правил:

line();

Х есть вершина дерева Т, если

корень дерева Т совпадает с X, или

Х - это вершина из левого поддерева, или

Х - это вершина из правого поддерева.

line();



Рис. 9. 5.  Представление двоичных деревьев.

Эти правила непосредственно транслируются на Пролог следующим образом:

        внутри( X, дер( -, X, -) ).

        внутри( X, дер( L, -, -) ) :-

                внутри( X, L).

        внутри( X, дер( -, -, R) ) :-

                внутри( X, R).

Очевидно, что цель

        внутри( X, nil)

терпит неудачу при любом X.

Посмотрим, как ведет себя наша процедура. Рассмотрим рис. 9.4. Цель

        внутри( X, Т)

используя механизм возвратов, находит все элементы данных, содержащиеся в множестве, причем обнаруживает их в следующем порядке:

        Х = а; Х = b; Х = с; X = d

Теперь рассмотрим вопрос об эффективности.

Содержание  Назад  Вперед

---

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий

---

---

---