Реферат: Алгоритмические языки и программирование

няются различные способы просмотра и перебора узлов.Основная

особенность каждого обхода заключается в том, что просматрива-

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

обрабатывается ровно один раз.

Для бинарного дерева определены три способа обхода: прямой

или префиксный (корень - левое поддерево - правое поддере-

во),обратный или инфиксный (левое поддерево - корень - правое

поддерево) и концевой или постфиксный (левое поддерево - правое

поддерево - корень).

При обходе дерева используются рекурсивные процедуры или

стек.В прошитых деревьях используются дополнительные указатели

на наличие поддеревьев (LTAG и RTAG). Введение дополнительных

указателей не приводит к большому увеличению затрат памяти, но

позволяет при обходе отказаться от стека.

Надо отметить,что любое дерево общего вида можно представить

в виде двоичного, надо в исходном дереве у каждого узла соеди-

нить его сыновей от старшего к младшему и убрать все связи узла

с сыновьями, оставив только связь со старшим сыном.

Над деревьями удобно определить операции: чтение информаци-

онной части из узла дерева, создание дерева, присоединение к

узлу нового поддерева, удаление поддерева.

Особенно полезны деревья при сортировке.Алгоритм состоит в

том, что при просмотре данных очередной элемент помещается в

двоичное дерево. Ключ нового элемента сравнивается с ключом те-

кущего узла.Если указатель текущего узла NIL, то указатель на

новый узел добавляется в то место откуда был извлечен NIL.Если

ключ нового узла меньше ключа текущего узла, то поиск места для

нового узла продолжается в левом поддереве, если больше - в

правом.После того как все данные занесены в двоичное дерево