Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать неотразимый комплимент Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?

Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Деревья





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

Формально дерево определяется как конечное множество Т одного или более узлов со следующими свойствами:

1. существует один выделенный узел, а именно – корень данного дерева Т;

2. остальные узлы (за исключением корня) распределены среди m0 непересекающихся множеств Т1, …, Тm и каждое из этих множеств в свою очередь, является деревом; деревья Т1, …, Тm называются поддеревом данного корня.

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

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

 

 

       
 
   

 


a) b)

с) (A (B (H) (J) ) (C (D) (E(G)) (F) ) )

d)

Рис. 7.2 Способы изображения древовидных структур: а) обычная схема дерева; b) вложенные множества; c) список с отступами; d) вложенные скобки.

 

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

Важнейшим подмножеством деревьев являются так называемые бинарные деревья. Бинарное дерево это конечное множество узлов, которое может быть пустым, либо состоять из корня вместе с двумя другими бинарными деревьями. Другими словами каждый его узел может иметь 0, 1, .2 детей (но не более); мы будем различать левых и правых детей.

Решение многих алгоритмических задач приводит к необходимости работать с древовидными структурами, так например, алгоритмический анализ алгебраического выражения y=3ln(x+1) – a/x2 приводит к построению дерева вида:

 

Обход в прямом порядке : посетить корень первого дерева; пройти поддеревья первого дерева; пройти оставшиеся деревья.

- * 3 ln + x 1 / a ^ x 2

Обход в обратном порядке : пройти поддеревья первого дерева; посетить корень первого дерева; пройти оставшиеся деревья. 3 x 1 + ln * a x 2 ^ / -

 






Date: 2015-05-22; view: 247; Нарушение авторских прав

mydocx.ru - 2015-2019 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию