PrintTree(Root,0)Пример 3.6. Описать процедуру MaxEl, определяющую наибольший Алгоритм MaxEl использует префиксный обход дерева: наибольший элемент находится или в узле, или в его левом поддереве, или в его правом procedure MaxEl(T: Tree; var max: integer); var m: integer; Begin if T <> nil then Begin max:=T^.inf; if T^.L <> nil then Begin MaxEl(T^.L, m); if m > max then max:=m End; if T^.R <> nil then Begin MaxEl(T^.R, m); if m > max then max:=m End End end; { MaxEl } Пример 3.7. Описать рекурсивную процедуру Leaf подсчета количества k листьев дерева. procedure Leaf(T: Tree; var k: integer); Begin if T <> nil then if (T^.L=nil) and (T^.R=nil) then k:=k+1 Else Begin Leaf(T^.L,k); Leaf(T^.R,k) End end; { Leaf } Количество List листьев дерева Root можно определить, обратившись к процедуре Leaf: List:=0; Leaf(Root,List); Если описать реализацию в виде функции, то не придется заботиться о присваивании нуля параметру–результату перед ее вызовом. function fLeaf (T: Tree): integer; Begin if T=nil then fLeaf:=0 Else if (T^.L=nil) and (T^.R=nil) then fLeaf:=1 else fLeaf:= fLeaf(T^.L)+fLeaf(T^.R) end {fLeaf}; Пример 3.8. Описать рекурсивную функцию Double, которая проверяет, есть ли в дереве T хотя бы два одинаковых элемента. Один из вариантов проверки состоит в использовании функции Count подсчета числа вхождений заданного элемента El в дерево T. Функция Double поочередно проверяет число вхождений текущего значения T^.inf в дерево: если число вхождений больше 1, то результат проверки – истина, если нет, то такая ситуация может возникнуть в левом поддереве или в правом поддереве. function COUNT(T: Tree; El:integer): integer; var k: integer; Begin if T=nil then COUNT:=0 Else Begin if T^.inf = El then k:=1 else k:=0; COUNT:=k+COUNT(T^.L,El)+COUNT(T^.R,El) End end; { COUNT } function Double(T: Tree): boolean; Begin if T=nil then Double:=false Else Begin if COUNT(T,T^.inf) > 1 then Double:=true Else Double:= Double(T^.L) or Double(T^.R) End end; { Double } Пример 3.9. Описать функцию Equal проверки на равенство двух двоичных деревьев одинаковой структуры. function Equal(T1,T2: Tree): boolean; Begin if T1=T2 then Equal:=true Else if (T1 <> nil) and (T2 <> nil) then if T1^.inf = T2^.inf then Equal:=Equal(T1^.L,T2^.L) and Equal(T1^.R,T2^.R) else Equal:=false else Equal:=false end; { Equal } Пример 3.10. Описать процедуру Copy, которая создает копию T2 procedure Copy(T1: Tree; var T2: Tree); Begin if T1 = nil then T2:=nil Else Begin new(T2); T2^.inf:=T1^.inf; Copy(T1^.L,T2^.L); Copy(T1^.R,T2^.R); End end; { Copy } Упражнение 3.2. Описать нерекурсивную процедуру или функцию, которая возвращает элемент из самого левого (правого) листа непустого дерева. Упражнение 3.3. Описать нерекурсивную процедуру или функцию, которая а) определяет количество узлов дерева; б) вычисляет сумму (произведение, среднее арифметическое) всех элементов дерева. в) определяет число вхождений заданного элемента в дерево; г) выдает элементы из всех листьев дерева. Упражнение 3.4. Описать рекурсивную процедуру или функцию, которая а) определяет количество узлов (листьев, внутренних узлов) дерева; б) вычисляет сумму (произведение, среднее арифметическое) всех элементов дерева. в) определяет, входит ли заданный элемент в дерево; г) выдает элементы из всех листьев (внутренних узлов) дерева; д) определяет глубину непустого дерева; е) определяет количество узлов на заданном уровне; ж) удаляет листья дерева со значениями, равными заданному.
4. ДЕРЕВО ПОИСКА (СОРТИРОВКИ)
Двоичные деревья могут использоваться для представления множества данных, в котором идет поиск элементов по уникальному значению или ключу. Если дерево организовано так, что для каждой вершины все ключи левого поддерева меньше ее ключа, а ключи правого поддерева больше его, то такое дерево называется деревом поиска или деревом сортировки (рисунок 6). 4.1 Построение дерева поиска Алгоритм создания дерева поиска основан на следующих правилах: Если новый элемент меньше, чем значение в узле, то он должен добавляться в левое поддерево, если больше, то в правое. Если в дереве есть узел с таким значением, то возможны варианты: а) новый узел добавляется в правое поддерево, б) новый узел добавляется в левое поддерево, в) добавление не происходит. Инфиксный обход такого дерева дает упорядоченную по возрастанию Пример 4.1. Упорядочить по неубыванию последовательность целых чисел, которая вводится из текстового файла.
|
