18 (1106255)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Курс «Алгоритмы и алгоритмические языки»1 семестр 2013/2014Лекция 181Двоичное деревоПредставление двоичного дерева в памяти компьютераОписание узла двоичного дерева на Си:typedef struct bin_tree {char info;struct bin_tree *left;struct bin_tree *right;} node;2Двоичное деревоОбход двоичного дерева.Обход дерева позволяет выполнить топологическую сортировкуузлов дерева и расположить их в линейном одномерноммассиве, порядок узлов дерева в котором таков, что их можнообрабатывать в циклеfor (i = 0; i < N; i++)(топологический порядок)3Двоичное деревоРазличные способы обхода двоичного дерева(1)Обход в глубину в прямом порядке:обработать корень,обойти левое поддерево,обойти правое поддерево.Порядок обработки узлов дерева на рисункеA B D C E G F H JЛинейная последовательность узлов, полученнаяпри прямом обходе, отражает «спуск» информацииот корня дерева к листьям.4Двоичное деревоРазличные способы обхода двоичного дерева(2)Обход в глубину в обратном порядке:обойти левое поддерево,обойти правое поддерево,обработать корень.Порядок обработки узлов дерева на рисунке:D B G E H J F C AЛинейная последовательность узлов, полученнаяпри обратном обходе, отражает «подъем»информации от листьев к корню дерева.5Двоичное деревоРазличные способы обхода двоичного дерева(3)Симметричный обход в глубину (обход всимметричном порядке):обойти левое поддерево,обработать корень.обойти правое поддерево,Порядок обработки узлов дерева на рисунке:D B A E G C H F J6Двоичное деревоРазличные способы обхода двоичного дерева(4)Обход двоичного дерева в ширину:узлы дерева обрабатываются «по уровням»(уровень составляют все узлы, находящиеся наодинаковом расстоянии от корня)Порядок обработки узлов дерева на рисунке:A B C D E F G H J7Двоичное деревоФункции, реализующие обходы двоичного дерева, позволяютпо указателю каждого узла дерева P вычислить указатели узловP_next_pre, P_next_post и P_next_in,P_pred_pre, P_pred_post и P_pred_in.Рекурсивные Си-функции обхода двоичного дерева вглубину(1)void preorder (node * r) {if (r == NULL)return;if (r->info)printf ("%c", r->info);preorder (r->left);preorder (r->right);}8Двоичное деревоРекурсивные Си-функции обхода двоичного дерева вглубину(2)void postorder (node *r) {if (r == NULL)return;postorder (r->left);postorder (r->right);if (r->info)printf ("%c", r->info);}(3)void inorder (node *r) {if (r == NULL)return;inorder (r->left);if (r->info)printf ("%c", r->info);inorder (r->right);}9Двоичное деревоНерекурсивная функция обхода двоичного дерева(управление стеком ведется не автоматически, а в самойфункции).r –указатель на корень дерева;t –указатель на корень обрабатываемого(текущего) поддерева;stack –массив,на котором моделируется стек,depth –глубина стека,top –указатель вершины стека;Стек требуется для ручного сохранения параметров функции,локальных переменных и точки возврата (если рекурсивныхвызовов функции несколько).В функции inorder нет локальных переменных, а второй из двухрекурсивных вызовов хвостовой, что позволяет не сохранятьего параметры в стекеПоэтому сохраняется только параметр функции10Двоичное деревоНерекурсивная функция обхода двоичного дереваАлгоритм:(1)[Инициализация].

Сделать стек пустым, т.е.затолкнуть NULL на дно стека: stack[0] = NULL;установить указатель стека на дно стека: top = 0;установить указатель t на корень дерева: t = r.(2)[Конец ветви].Если t == NULL, перейти к (4).(3)[Продолжение ветви]. Затолкнуть t в стек:stack[++top] = t;установить t = t->left и вернуться к шагу (2).(4)[К обработке правой ветви]. Вытолкнуть верхнийэлемент стека в t: t = stack[top]; top--;Если t == NULL, выполнение алгоритмапрекращается, иначе обработать данные узла, накоторый указывает t, и перейти к шагу (5).(5)[Начало обработки правой ветви].

Установитьt = t->right и вернуться к шагу (2).11Двоичное деревоНерекурсивная функция обхода двоичного дереваint inorder (node *r, char *order) {node *t = r;node *stack[depth];// depth = ?int top = 0, i = 0;if (!t)return 0;stack[0] = NULL;while (1) {while (t) {stack[++top] = t;t = t->left;}t = stack[top--];if (t) {order[i++] = t->info;t = t->right;} elsebreak;}return i;}//Шаг 1//Шаг 2//Шаг 3//Шаг 4//обработка//Шаг 512Двоичное деревоПрошитое двоичное деревоРассмотрим двоичноедерево на верхнемрисунке.У этого дерева нулевыхуказателей, больше,чем ненулевых:10 против 8.Это – типичный случай.Будем записыватьвместо нулевыхуказателей указателина родителей (илиболее далеких предков)соответствующих узлов(такие указателиназываются нитями).Это позволит приобходе дерева неиспользовать стек.13Двоичное деревоПрошитое двоичное деревоОписание узла прошитого двоичного дереваtypedef struct bin_tree {char info;struct bin_tree *left;struct bin_tree *right;char left_tag;char right_tag;} threaded_node;Нитиустанавливаютсятаким образом,чтобы указывать напредшественников(левые нити) илипоследователей(правые нити)текущего узла присоответствующемобходе дерева.Например, в случаесимметричногообхода:Обычное деревоПрошитое деревоP->left == NULLP->left_tag == 1, P->left == P_pred_inP->left == QP->left_tagP->right == NULLP->right_tag == 1, P->right == P_next_inP->right == QP->right_tag == 0, P->right == Q== 0, P->left== Q14Двоичное деревоПрошитое двоичное деревоНити существенно упрощают алгоритмы обхода двоичныхдеревьев.

Например, для вычисления для каждого узла pуказатель узла P_next_in можно использовать следующийпростой алгоритм:threaded_node * next_in (threaded_node *p) {threaded_node *q = p->right;if (p->right_tag == 1)return q;while (q->left_tag == 0) //q != NULLq = q->left;//q->left != NULLreturn q;}Функция next_in фактически реализует симметричныйобход дерева, так как позволяет для произвольного узладерева P найти P_next_in. Многократно применяя этуфункцию, можно вычислить топологический порядок узловдвоичного дерева, соответствующий симметричному обходу.15Двоичное деревоПрошитое двоичное деревоАналогичным образом можно вычислить P_next_pred иP_next_post.Применяя функции next_pred (либо next_post), можновычислить топологический порядок узлов, соответствующийпрямому (либо обратному) обходу.Замечания(1)С помощью обычного представления невозможно дляпроизвольного узла P вычислить P_next_in, невычисляя всей последовательности узлов.(2)Функции next_in не требуется стек ни в явной, нив неявной (рекурсия) форме.16Двоичное деревоПрошитое двоичное деревоСравнение функций inorder()и next_in()позволяет сделать следующие выводы:Если p – произвольно выбранный узел дерева,тоследующий фрагмент функции next_in():q = p->right;if (p->right_tag == 1)return q;выполняется только один раз.Обход прошитого дерева выполняется быстрее, так какдля него не нужны операции со стеком.Для inorder() требуется больше памяти, чем дляnext_in(), из-за массива stack[depth].depth стараются взять не очень большим, но depth неможет быть меньше высоты двоичного дерева.Нельзя допускать переполнение стека деревьев.17Двоичное дерево Прошитое двоичное деревоВ функции inorder() используетсяуказатель r на корень двоичного дерева.Желательно, применив функцию next_in()к корню r, получить указатель на самыйпервый узел дерева для выбранногопорядка обхода.

Для этого к деревудобавляется еще один узел –заголовок дерева (header).поля структурыtypedef struct bin_tree{char info;struct bin_tree *left;struct bin_tree *right;char left_tag;char right_tag;} threaded_node;threaded_node *header;заполняются в заголовкеследующим образомheader->left_tag = 0;header->right_tag = 0;header->left = r;header->right = header;На рисунке дугидерева показаны болеежирными линиями, 18чем нити..

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций