Печать результатов сортировки.

Печать результатов сортировки. Для того чтобы напечатать в алфавитном порядке результаты сортировки слов, включенных в вершины дерева, необходима функция обхода дерева по определенному маршруту. Сначала рассмотрим пример небольшого бинарного дерева, приведенный на рис. 8.20.

Рис. 8.20. Пример бинарного дерева

Такое дерево легко получится при вводе, например, такой последовательности букв латинского алфавита: D, В, С, F, А, Е, G (введены все буквы в диапазоне от А до G). Рассматривая это дерево, можно заметить, что буквы А и G (открывающая и закрывающая отсортированную последовательность) расположены на третьем (нижнем) уровне, соответственно слева и справа. Для того чтобы напечатать буквы в алфавитном порядке, необходимо спуститься от корня дерева по левым ветвям до самой нижней вершины. Там и будет первый элемент отсортированной последовательности букв. Увидев, что левый указатель равен NULL, напечатаем А и проверим указатель правой ветви. Он также равен NULL, поэтому поднимемся к предыдущей вершине и напечатаем В. Спускаемся от В по правой ветви к С и видим, что вниз по левой ветви от С указатель равен NULL, следовательно, печатаем С. Далее идем вверх к В (эта буква уже напечатана), поднимаемся к D и печатаем ее.

Аналогичным образом обходим правое от D поддерево. В итоге получается маршрут, изображенный на рис. 8.21.

Рис. 8.21. Обход бинарного дерева при печати

Ниже приводится текст функции print(), осуществляющей обход дерева и печать строк из вершин в алфавитном порядке. Для запоминания указателей на предыдущие узлы в функции организован стек глубиной 10 элементов в виде массива из 10 указателей на структуру типа struct node.

Оператор stack[i++] = ptr; заносит в стек значение указателя ptr и затем (постфиксная операция ++) увеличивает значение индекса (!) массива на 1. После этого stack[i] становится первым свободным элементом стека. Для выборки из стека значения указателя необходимо сначала уменьшить индекс i на единицу, с тем, чтобы stack[i] был не первым свободным элементом массива, а последним записанным:

Текст функции print( ):

Подробно процесс подготовки и выполнение программы сортировки на основе бинарного дерева в операционных системах UNIX, MS-DOS и Windows обсуждаются в главе 9.