Практикум по курсу "Алгоритмизация и программирование". Часть 2. Андрианова А.А - 96 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова .
// печатаем информационное поле узла root
printf("%d ",root->info);
// печатаем значения из правого
// поддерева узла root
PrintTree(root->right);
}
}
При написании нерекурсивного варианта функции печати требуется ис-
пользовать стек. Для возвращения к вершинам верхнего уровня, в нем нужно
хранить адреса уже пройденных вершин.
В таблице 2 поясняется процесс печати элементов дерева, изображенного
на рис. 6.1, в порядке неубывания.
Таблица 2. Печать элементов дерева.
Содержимое по
адресу temp
Состояние
стека
Выходная
строка
Комментарии
17 Пуст
6 17
Начинаем движение до крайнего
левого листового узла
5 17, 6
NULL 17, 6, 5
Левого потомка узла «5» не су-
ществует.
5 17, 6 5
Извлекаем из стека элемент 5,
выводим на печать. Переходим к
правому потомку узла «5».
NULL 17, 6
Правого потомка узла «5» тоже
не существует. Поэтому перехо-
дим к родительскому узлу «6»,
извлекая его из стека.
6 17 5, 6
Переходим к правому потомку
узла «6»
9 17
Начинаем движение влево.
7 17, 9
96
А.А. Андрианова, Л.Н. Исмагилов, Т.М. Мухтарова                               .
                   // печатаем информационное поле узла root
                   printf("%d ",root->info);
                   // печатаем значения из правого
                   // поддерева узла root
                   PrintTree(root->right);
              }
    }

    При написании нерекурсивного варианта функции печати требуется ис-
пользовать стек. Для возвращения к вершинам верхнего уровня, в нем нужно
хранить адреса уже пройденных вершин.
    В таблице 2 поясняется процесс печати элементов дерева, изображенного
на рис. 6.1, в порядке неубывания.

                                                  Таблица 2. Печать элементов дерева.

 Содержимое по       Состояние       Выходная
                                                            Комментарии
  адресу temp          стека          строка
         17             Пуст
                                                   Начинаем движение до крайнего
         6               17                        левого листового узла

         5              17, 6
                                                   Левого потомка узла «5» не су-
        NULL           17, 6, 5                    ществует.

                                                   Извлекаем из стека элемент 5,
         5              17, 6            5         выводим на печать. Переходим к
                                                   правому потомку узла «5».

                                                   Правого потомка узла «5» тоже
                                                   не существует. Поэтому перехо-
        NULL            17, 6                      дим к родительскому узлу «6»,
                                                   извлекая его из стека.

                                                   Переходим к правому потомку
         6               17             5, 6       узла «6»

         9               17                        Начинаем движение влево.

         7              17, 9




                                             96

Страницы