Нужно реализовать функции по паскалю, желательно отдельно каждую - Pascal
Формулировка задачи:
следующие функции:
−построение в связной памяти бинарного поискового дерева по дан- ным из файла на основе операции поиска вставкой;
−поиск вершин, у которых количество потомков в левом поддереве от- личается от количества потомков в правом поддереве на единицу, на основе ре- курсивного алгоритма восходящего обхода;
−нахождение высоты дерева на основе итеративного алгоритма нисходящего обхода;
−поиск k-гов порядке слева направо листа дерева(k задается пользова- телем) на основе рекурсивного алгоритма смешанного обхода;
−удаление вершины по ключу, заданному пользователем, на основе операции поиска исключением.
Решение задачи: «Нужно реализовать функции по паскалю, желательно отдельно каждую»
textual
Листинг программы
const fName = 'tree.dat'; /// Создание файла (ибо у меня небыло начальных данных ;-) procedure createFile; begin randomize; var f : Text; Rewrite(f, fName); for var i := 1 to 1000 do WriteLn(f, Random(-5000, +5000)); Close(f); end; type tTree = class V : Integer; L, R : tTree; constructor (V : Integer); begin Self.V := V; L := nil; R := nil; end; procedure Add(V : Integer); begin if V < Self.V then if L = nil then L := New tTree(V) else L.Add(V) else if V > Self.V then if R = nil then R := New tTree(V) else R.Add(V); end; function Count : Integer := 1 + (L = nil ? 0 : L.Count) + (R = nil ? 0 : R.Count); function Width := 1 + max(L = nil ? 0 : L.Count, R = nil ? 0 : R.Count); function Get(var k : Integer) : integer; begin k -= 1; if k = 0 then Result := V else begin if L <> nil then Result := L.Get(k); if (k > 0) and (R <> nil) then Result := R.Get(k); end; end; function inTree(V : Integer) : Boolean; begin case Sign(V - Self.V) of -1 : Result := L <> nil ? L.inTree(V) : False; 0 : Result := True; +1 : Result := R <> nil ? R.inTree(V) : False; end; end; end; // tTree /// Создание бинарного дерева из файла function createTree : tTree; begin Result := nil; var v : Integer; foreach var s in ReadLines(fName) do begin if TryStrToInt(s, v) then if Result = nil then Result := New tTree(v) else Result.Add(v); end; end; function almostEqual(Tree : tTree) : Integer; begin var L := (Tree.L = nil ? 0 : Tree.L.Count); var R := (Tree.R = nil ? 0 : Tree.R.Count); Result := (Abs(L - R) = 1 ? 1 : 0); if Tree.L <> nil then Result += almostEqual(Tree.L); if Tree.R <> nil then Result += almostEqual(Tree.R); end; function searchSheet(k : Integer; Tree : tTree) : String; begin if k < 1 then Result := 'номер листа - это натуральное число!' else if k > Tree.Count then Result := 'количество листов в дереве меньше заданного значения!' else Result := Tree.Get(k).ToString; end; begin { раскомментировать для того, чтобы создать файл с высотой дерева не более 500 } //repeat // createFile; //until createTree.Width < 500; var Tree := createTree; WriteLn('Дерево сформировано. Общее количество элементов = ', Tree.Count); WriteLn; WriteLn('Количество вершин, у которых количество потомков в левом поддереве'); WriteLn(' отличается от количества потомков в правом поддереве на единицу = ', almostEqual(Tree)); WriteLn; WriteLn('Высота дерева = ', Tree.Width); WriteLn; WriteLn('Значение искомого листа = ', searchSheet(ReadInteger('Номер искомого листа: k ='), Tree)); end.