Используя этот тип данных узлов двоичного дерева, функцию create (листинг 3.9) можно переписать так, как показано в следующем листинге.

Листинг 3.11. Код функции create при реализации двоичного дерева с помощью указателей

function create ( lefttree, righttree: tnode) : tnode; var

root: Tnode; begin

new{root) ;

roott. leftchild:= lefttree; roott .rightchild:- righttree; roott .parent: 0; lefttreeT.parent: = root; j-igAttreet.parent: = root; return (root) end; { create }

Упражнения

3.1. Ответьте на следующие вопросы о дереве, показанном на рис. 3.18:

а) какие узлы этого дерева являются листьями?

б) какой узел является корнем дерева?

в) какой узел является родителем узла С?

г) назовите сыновей узла С;

д) назовите предков узла Е\

е) назовите потомков узла Е;

ж) какие узлы являются правыми братьями узлов D и Е?

з) какие узлы лежат слева и справа от узла G?

и) какова глубина узла С? к) какова высота узла С?

М N

Рис. 3.18. Дерево

3.2. Сколько путей длины 3 существует на дереве, показанном на рис. 3.18?

3.3. Напищите программы вычисления высоты дерева с использованием трех представлений деревьев, описанных в разделе 3.3.

3.4.

3.5.

3.6.

3.7.

*3.8.

3.9.

Составьте списки узлов дерева, представленного на рис. 3.18, при обходе этого дерева

а) в прямом порядке;

б) в обратном порядке;

в) во внутреннем порядке.

Пусть два различных узла тип принадлежат одному и тому же дереву. Покажите, что только одно из следующих утверждений может быть истинным:

а) узел т расположен слева от узла га;

б) узел т расположен справа от узла п;

в) узел т - истинный предок узла п;

г) узел т - истинный потомок узла п.

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

Узел п предшествует узлу т. при обходе дерева в обратном порядке

Узел га предшествует узлу т при обходе дерева в прямом порядке

Узел п предшествует узлу т при симметричном обходе дерева

Узел п расположен слева от узла т. Узел п расположен справа от узла т

Узел п - истинный предок

уЗЛа т

Узел п - истинный потомок УЗЛа т

Например, поставьте галочку в ячейку на пересечение третьей строки и второго столбца, если уверены, что узел п может быть истинным предком узла т и в тоже время предшествовать узлу т при обходе дерева в обратном порядке.

Предположим, что есть массивы PREORDER[ra], INORDER[ra] и POSTORDER[n],

содержащие списки узлов дерева, полученные при его обходе в прямом, внутреннем и обратном порядке соответственно. Используя эти массивы, опишите алгоритм, который для любой пары узлов / и j определяет, является ли узел i предком узла /

Существует способ проверить, является ли один узел истинным предком другого узла, который основан на следующем правиле: узел т является истинным предком узла п, если узел т. предшествует узлу п при обходе дерева в X порядке, но следует за узлом п при обходе в Y порядке, где X и Y выбираются из множества {прямом, обратном, внутреннем). Определите все возможные пары X и Y, когда это правило справедливо.

Напишите программы обхода двоичных деревьев

а) в прямом порядке;

б) в обратном порядке;

в) во внутреннем порядке.

3.10. При прохождении дерева в порядке уровней в список узлов сначала заносится корень дерева, затем все узлы глубины 1, далее все узлы глубины 2 и т.д. Узлы одной глубины заносятся в список узлов в порядке слева направо. Напишите программу обхода деревьев в порядке уровней.

3.11. Преобразуйте выражение {(а + Ь) + с * (d + е) +f) * (g + h)

а) в префиксную форму;

б) в постфиксную форму.

3.12. Нарисуйте дерево, соответствующее префиксным выражениям

а) *а + Ь*с + de\

б) *а + *Ь + cde.

3.13. Пусть Т - дерево, в котором каждый узел, не являющийся листом, имеет ровно двух сыновей. Напишите программы преобразования

а) списка узлов дерева Т, составленного при обходе дерева в прямом порядке, в список, составленный при обходе в обратном порядке;

б) списка узлов дерева Т, составленного при обходе дерева в обратном порядке, в список, составленный при обходе в прямом порядке;

в) списка узлов дерева Т, составленного при обходе дерева в прямом порядке, в список, составленный при симметричном обходе.

3.14. Напишите программу вычисления арифметических выражений при обходе дерева

а) в прямом порядке;

б) в обратном порядке.

3.15. Двоичное дерево можно определить как АТД со структурой двоичного дерева и операторами LEFTCHILD(ra), RIGHTCHILD(ra), PARENT(n) и NULL(ra). Первые три оператора возвращают соответственно левого сына, правого сына и родителя узла п (если такового нет, то возвращается Л). Последний оператор возвращает значение true тогда и только тогда, когда дерево с корнем п является нулевым. Реализуйте эти операторы для двоичного дерева, представленного в табл. 3.1.

3.16. Напишите процедуры для семи операторов деревьев из раздела 3.2, используя следующие реализации деревьев:

а) указатели на родителей;

б) список сыновей;

в) указатели на самого левого сына и на правого брата.

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

3.18. Докажите, что в любом двоичном дереве высотой h количество узлов не пре-

вышает 2" - 1. Двоичное дерево высотой h с максимально возможным количеством узлов называется полным двоичным деревом.

*3.19. Предположим, что дерево реализуется с помощью указателей на самого левого сына, на правых братьев и на родителя. Разработайте алгоритмы обхода деревьев в прямом, обратном и внутреннем порядке, не используя при этом стека, как сделано в листинге 3.3.

3.20. Пусть символы а, Ь, с, d, е и f имеют вероятности появления соответственно 0.07, 0.09, 0.12, 0.22, 0.23, 0.27. Найдите оптимальный код Хаффмана и нарисуйте соответствующее ему дерево. Какова средняя длина кода?