Методические указания к лабораторным работам по курсу “




Скачать 328.11 Kb.
НазваниеМетодические указания к лабораторным работам по курсу “
страница3/5
Дата публикации01.04.2013
Размер328.11 Kb.
ТипМетодические указания
vbibl.ru > Биология > Методические указания
1   2   3   4   5
^

Обход дерева



Существует несколько режимов обхода дерева: прямой, обратный, конечный и т.д. Рассмотрим алгоритм прямого обхода.
1. Если дерево пусто – конец.

2. В противном случае, обработать текущий узел, затем обойти его левое поддерево, а затем обойти его правое поддерево.

В терминах Пролга этот алгоритм реализуется с помощью двух фраз:
traverse(empty).

traverse(tree(X,Y,Z):- do something with X, traverse(Y),

traverse(Z).
Рассмотрим программу обхода дерева, которая печатает его узлы.

domains

treetype = tree(string, treetype, treetype);

empty()

predicates

print_all_elements(treetype)

clauses

print_all_elements(empty).

print_all_elements(tree(X,Y,Z)):- write(X), nl,

print_all_elements(Y),

print_all_elements(Z).

goal: print_all_elements(tree("Cathy", tree("Michael",

tree("Charles", empty, empty),

tree("Hazel", empty, empty)),

tree("Melody", tree("Jim", empty,

empty), tree("Eleanor", empty,

empty)))).

^

Создание дерева



Создание корневого узла:
create_tree(N, tree(N,empty,empty)).
Далее требуется фраза для вставки левого поддерева. Она имеет три аргумента: первый – вставляемое дерево, второй – модифицируемое дерево, третий аргумен содержит результирующее древо.
insert_left(X, tree(A, _ , B), tree(A,X,B)).
Предположим, что требуется вставить дерево
tree('Michael ' , empty, empty)
как левое поддерево в
tree('Cathy', empty, empty).
Это можно сделать с помощью запроса:
goal : insert_left(tree('Michael',empty,empty),

tree('Cathy',empty,empty),T).

где T примет значение tree('Cathy', tree(Michael',empty,empty), empty).
Используя этот подход можно построить все дерево.

/* * * * * * * * * * * * * * * * * * * * * * * * * * * *

* create_tree(A, B) вставляет A в поле данных дерева B

* insert_left(A, B, C) вставляет A как левое поддерево

* B, получая дерево C *

* insert_right(A, B, C) вставляє A как правое поддерево

* B, получая дерево С *

**** * * * * * * * * * * * * * * * * * * * * * * * */

domains

treetype = tree(string, treetype, treetype);

empty()

predicates

create_tree(string, treetype)

insert_left(treetype, treetype, treetype)

insert_right(treetype, treetype, treetype)

clauses

create_tree(A, tree(A, empty, empty)).

insert_left(X, tree(A, _, B), tree(A, X, B)).

insert_right(X, tree(A, B,_), tree(A, B, X)).

goal :

/* Спочатку створимо вузли (однорівневі дерева)... */

create_tree("Charles", Ch), create_tree("Hazel", H),

create_tree("Michael", Mi), create_tree("Jim", J),

create_tree("Eleanor", E), create_tree("Melody",Me),

create_tree("Cathy", Ca),

/* ... потім встановимо зв`язки */

insert_left(Ch, Mi, Mi2), insert_right(H , Mi2, Mi3),

insert_left(J, Me, Me2), insert_right(E , Me2, Me3),

insert_left(Mi3,Ca, Ca2), insert_right(Me3, Ca2, Ca3),

/* ... і роздрукуємо результат. */

write(Ca3), nl.

^ Бинарный поиск в дереве.
Рассмотрим специальный тип бинарного дерева, которое называют бинарным деревом поиска.

Алгоритм его построения:

1. Если текущий узел есть пустое дерево, вставить в него элемент.

2. Иначе, сравнить элемент, подлежащий вставке с элементом текущего узла. Если значение вставляемого узла меньше, втавить его в левое поддерево текущего узла, в противном случае – вставить его в правое поддерево.
Реализация алгоритма в терминах Пролога требует трех фраз.

Первая:

insert(NewItem,empty, tree(NewItem,empty,empty):-!.
Т.е. результатом вставки элемента NewItem в пустое дерево есть дерево

tree(NewItem, empty,empty) .
Вторая и третья фразы реализуют соответственно лево- и правосторонние вставки в непустое дерево:
insert(NewItem,

tree(Element,Left,Right),

tree(Element,NewLeft,Right):- NewItem < Element, !,

insert (NewItem, Left, NewLeft).

insert(NewItem,

tree(Element,Left,Right),

tree(Element, Left, NewRight)):-

insert(NewItem, Right, NewRight).
^ Сортировка по дереву
Если бинарное дерево поиска уже построено, размещение его элементов в лексикографическом порядке выполняется очень просто. Рекурсивный алгоритм обратного обхода дерева имеет вид.
1. Если дерево пусто – завершить алгоритм.

2. Иначе, просмотреть все узлы левого поддерева, затем текущий узел, затем все узли првого поддерева.
Т.о.:
retrieve_all(empty).

retrieve_all(tree(Item,Left,Right)):- retrieve_all(Left),

do_something_to(Item),

retrieve_all(Right).
Т.о. временная сложность упорядочивания элементов дерева составляет О(N logN).

1   2   3   4   5

Похожие:

Методические указания к лабораторным работам по курсу “ iconФизика методические указания к лабораторным работам 10, 31
Козлов В. А., Курушин А. Д., Серов Е. А. Физика. Методические указания к лабораторным работам 10, 31 // Под общ ред доц. С. Г. Стоюхина....

Методические указания к лабораторным работам по курсу “ iconМетодические указания и задания к лабораторным работам по курсу "алгоритмы и структуры данных "
Методические указания предназначены для усвоения теоретических основ и формирования практических навыков по выбору рациональных структур...

Методические указания к лабораторным работам по курсу “ iconМетодические указания к лабораторным наборам предназначены для студентов,...
Металлургическая гидроаппаратура: Методические указания к лабораторным работам / Санкт-Петербургский государственный горный институт...

Методические указания к лабораторным работам по курсу “ iconМетодические указания к лабораторным работам по дисциплине «Программирование»
Тема: Разработка классов, создание конструкторов и деструкторов. Использование статических членов класса

Методические указания к лабораторным работам по курсу “ iconМетодические указания к лабораторным работам по дисциплине «Автоматизация...
Сапр простейшей структуры на основе расчета и анализа критериев эффективности с использованием имитационных моделей

Методические указания к лабораторным работам по курсу “ iconУчебное пособие к лабораторным работам
Автоматизированные информационно-управляющие системы: учебное пособие к лабораторным работам / Л. С. Казаринов, Т. А. Барбасова,...

Методические указания к лабораторным работам по курсу “ iconМетодические указания и задания к лабораторным работам по курсам “
Дискретные структуры“, “Теория алгоритмов и вычислительных процессов“ (для студентов специальностей 050102 “Программное обеспечение...

Методические указания к лабораторным работам по курсу “ iconМетодические указания к лабораторным работам по учебным дисциплинам...
«Электродинамика и распространение радиоволн», «Техническая электродинамика» (для студентов направлений подготовки 050901 «Радиотехника»,...

Методические указания к лабораторным работам по курсу “ iconПрактикум по компьютерному моделирования ядерных процессов с использованием...
Практикум по компьютерному моделирования ядерных процессов с использованием библиотеки geant4

Методические указания к лабораторным работам по курсу “ iconМетодические указания по анализу финансового 12 состояния организации 12
Методические указания предназначены для выполнения курсовых работ по дисциплине «Анализ хозяйственной деятельности» для студентов...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница