покажчиками на наступні вузли, відповідні обходу. Сімметрічноправая прошивка увазі обхід зліва-направо. <В
Малюнок 6 - Сімметрічноправая прошивка дерева
Процедура прошивки, в якій здійснюється обхід, проводить пошук листя і вузлів, для яких потрібно прошивка (зокрема це листя 3, 7, 9 і вузол 4). Коли цей лист або вузол виявляється, ініціалізується додаткова процедура, яка таким же обходом знаходить вузол, до якого прошивається лист або вузол, знайдений первинної процедурою (3, 7, 9 і 4). Такими вузлами є 4, 5 і 8. p align="justify"> Висновки:
в ході виконання роботи були вивчені нелінійні динамічні структури даних у вигляді бінарного дерева;
була вирішена задача, пов'язана зі структурою даних - бінарне дерево (створення, подання, обходи та прошивка дерева).
Додаток
bin_tree; n = 8; pnode = ^ node;
node = record
v: integer;
right, left: pnode;
lf, rf: boolean;
end; root: pnode;
st: boolean; {прапорець для визначення прошито чи дерево}
v: integer;
right, left: pnode;
j, h, i, answ, answ2: integer; m: array [1 .. n] of integer = (5,4,8,6,1,7,3,9);
{------------ create of tree -------------} Insert (var root: pnode; X: integer);
{Додаткова процедура, що створює і ініціює новий вузол}
procedure CreateNode (var p: pnode; n: integer);
begin
new (p);
p ^. v: = n;
p ^. left: = nil;
p ^. right: = nil;
end;
if root = nil then
CreateNode (root, X) {створюємо новий вузол дерева}
else
with root ^ do
begin
if v
Insert (right, X)
else
if v> X then
Insert (left, X)
else
{Дії, вироблені у разі повторного внесення
елементів в дерево}
begin
writeln ('Такий елемент вже є');
exit;
end;
end;
;
{--------- View of tree --------------------} ViewTree (root: pnode); mas1 , mas2: array [1 .. 8] of integer;
q, m1, m2: integer;
Sch, Chl, Chr: pnode;
{функція для визначення кількості відступів}
function sc (s: integer): integer;
var c, c1, w: integer;
begin
c: = 0;
sc: = 0;
s: = s-1;
if s = 0 then
exit;
for w: = 1 to s do
begin
c1: = 1 +2 * c;
c: = c1;
end;
sc: = c1;
end;
{пошук вузла або листа дерева за значенням v}
procedure Search (root: pnode; s: integer);
begin
if root ^. v = s then
begin
Sch: = root;
exit;
end;
if root = nil then
exit
else
begin
Search (root ^. right, s);
Search (root ^. left, s);
end;
end;
{занесення нащадків вузлів дерева одного рівня в 2-ій масив}
procedure ToMas2;
begin
if Sch ^. left <> nil then
begin
Chl: = Sch ^. left;
m2: = m2 +1;
mas2 [m2]: = Chl ^. v;
end
else
begin
m2: = m2 +1;
mas2 [m2]: = 0;
end;
if Sch ^. right <> nil then
begin
Chr: = Sch ^. right;
m2: = m2 +1;
mas2 [m2]: = Chr ...