ВУЗ:
Составители:
Рубрика:
38
конец, правое поддерево в инфиксном порядке. При обходе корня следует вывес-
ти его поле данных:
procedure InfixPrintTree(r: PNode);
begin
if r=nil then
exit;
InfixPrintTree(r.left);
write(r.data,' ');
InfixPrintTree(r.right);
end;
Очевидно, если в последних трех операторах поместить оператор write на
первое место, то мы получим вывод дерева в префиксном порядке, если на по-
следнее, то в постфиксном.
Задача
4. Дано бинарное дерево. Найти его глубину.
Решение. Глубина дерева на единицу больше максимальной глубины его
поддеревьев. Поскольку глубина дерева из одного элемента равна 0, то естествен-
но считать глубину пустого дерева равной -1.
function TreeDepth(r: PNode): integer;
begin
if r=nil then
Result:=-1
else Re-
sult:=max(TreeDepth(r.left),TreeDepth(r.right))+1;
end;
Обратим внимание, что во всех задачах глубина рекурсии совпадает с
глубиной
дерева. Более того, если вызов подпрограммы представлять в виде узла дерева и
считать его сыновьями рекурсивные вызовы подпрогрмм, то множество всех ре-
курсивных вызовов образует дерево. Этот факт подчеркивает тесную связь де-
ревьев и рекурсии.
4.2 Бинарные деревья поиска (БДП)
Бинарное дерево называется бинарным деревом поиска (БДП, BST – Binary
Search Tree), если значение каждого его узла не меньше значений узлов левого
поддерева и не больше значений узлов правого поддерева.
Ниже на рисунке изображено полное бинарное дерева поиска глубины 3:
41
17 73
8
3 12
29
27 39
60
42 70
90
81 99
Страницы
- « первая
- ‹ предыдущая
- …
- 34
- 35
- 36
- 37
- 38
- …
- следующая ›
- последняя »
