Деревья

1) Какую структуру называют деревом?

2) Приведите примеры деревьев.

3) Назовите различные способы графического представления древовидной структуры.

4) Как с помощью массивов можно представить дерево?

5) Какая связь существует между числом вершин и числом ребер дерева?

6) Какое дерево называется упорядоченным?

7) Что называется глубиной или высотой дерева?

8) Что называется степенью дерева (вершины)?

9) Приведите пример двоичного дерева.

10)Какое дерево называется идеально сбалансированным?

11)Изобразите идеально сбалансированное дерево из 10 (13) вершин.

12)Напишите процедуры:

a) печати элементов дерева;

b) поиска по дереву элемента B (результат типа boolean);

c) поиска в упорядоченном дереве элемента B (результат типа boolean);

d) вставки в упорядоченное дерево элемента Y;

e) создания из массива упорядоченного дерева;

f) замены всех отрицательных элементов дерева на их модуль;

g) строящую дерево- копию исходного непустого дерева;

h) нахождения наибольшего элемента дерева.

13)Напишите функции:

a) подсчета количества вершин дерева;

b) подсчета числа вхождений элемента E в дерево;

c) вычисления суммы элементов дерева;

d) определения глубины непустого дерева;

e) вычисления среднего арифметического элементов дерева.

14)В следующих программах найдите смысловые ошибки и укажите реакцию машины на них, если есть описание:
type p=^element;
element=record
f: integer;
left, right: p end;

a) печать дерева

procedure print (x: p; h: integer);
var i: integer;
begin print (x^.left, h+1);
for i:=1 to h*10 do write (“ ”);
writeln (x^.f); writeln;
print (x^.right, h+1) end.

b) поиск элемента по дереву

procedure search (x: p; B: integer; var A: boolean);
begin if x^.f=B then A:=true else
while x<>nil do begin search (x^.left, B, A);
search (x^.right, B, A) end; A:=false end.

c) создание дерева-копии

procedure copy (x: p; var y: p);
begin if x<>nil then begin new (y); y^.f:=x^.f;
copy (x^.left, y^.left); copy (x^.right, y^.right)
end end.

d) нахождение глубины дерева

function depth (x: p): integer;
var h1,h2: integer;
begin if x=nil then depth:=-1 else
begin h1:=1+ depth (x^.left);
h2:=1+ depth (x^.right);
if h1>h2 then depth:=h1 else depth:=h2
end end.

e) создание из массива упорядоченного дерева

procedure search1 (k: integer; var x: p);
var i: integer;
begin i:=1; while i<>n do begin
if x=nil then begin new (x); x^.f:=A[i];
x^.left:=nil; x^.right:=nil end
else
if A[i]<x^.f then search1 (A[i], x^.left)
else
if A[i]>x^.f then search1 (A[i], x^.right);
i:=i+1 end end.

f) вычисление среднего арифметического

function sr (x: p): real;
var n: integer; S: real;
begin if x=nil then sr:=0 else
S:=0; n:=1;
while x<>nil do begin
S:=S*(n-1)/n+x^.f/n; n:=n+1;
sr (x^.left); sr (x^.right) end end.

g) нахождение наибольшего элемента

procedure max (x: p; var M: integer);
begin if x=nil then write (“наибольшего нет”) else
M:=x^.f; while x<>nil do max (x^.left, M);
if x^.f>M then M:=x^.f; max (x^.right, M) end end.