Форум программистов, компьютерный форум, киберфорум
Turbo Pascal
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.78/9: Рейтинг темы: голосов - 9, средняя оценка - 4.78
0 / 0 / 0
Регистрация: 07.09.2017
Сообщений: 24
1

Балансировка двоичного дерева

11.11.2017, 19:27. Просмотров 1801. Ответов 1
Метки нет (Все метки)

В файле дана последовательность целых чисел. Построить из них двоичное дерево поиска . Разработать процедуру перестройки двоичного дерева с целью сделать его более низким и симметричным (задача балансировки дерева). Использовать ее для балансировки сформированного ранее дерева. Применить рекурсию. У меня вопрос, как вывести итоговое сбалансированное дерево дерево в файл.
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
type
  t = ^uzel;
  uzel = record
    elem: integer;
    lf, rt: t;
  end;
 
procedure P1(var ukt1: t; c1: integer);
 
var
  uk: t;
 
begin
  new(uk);
  uk^.elem := c1;
  uk^.lf := nil;
  uk^.rt := nil;
  if ukt1 = nil then
  begin
    ukt1 := uk;
  end
  else
  begin
    if c1 > ukt1^.elem then
    begin
      P1(ukt1^.rt, c1);
    end
    else
    begin
      P1(ukt1^.lf, c1);
    end;
  end;
end;
 
procedure P2(root: t);
 
var
  ukz, S: t;
  max, h: integer;
 
begin
  max := 0;
  while (root^.lf <> nil) or (root^.rt <> nil) do
  begin
    S := root;
    h := 1;
    if root^.lf <> nil then ukz := root^.lf else ukz := root^.rt;
    while (ukz^.lf <> nil) or (ukz^.rt <> nil) do
    begin
      while ukz^.lf <> nil do
      begin
        S := ukz;
        ukz := ukz^.lf;
        h := h + 1;
      end;
      if ukz^.rt <> nil then
      begin
        S := ukz;
        ukz := ukz^.rt;
        h := h + 1;
      end;
    end;
    if S^.lf = ukz then S^.lf := nil else S^.rt := nil;
    if h > max then max := h;
  end;
  writeln(max);
end;
 
procedure P3(ukt2: t);
 
begin
  if ukt2 <> nil then writeln('Reading...', ukt2^.elem);
  if ukt2^.lf <> nil then writeln('Left: ', ukt2^.lf^.elem) else writeln('Left: nil');
  if ukt2^.rt <> nil then writeln('Right: ', ukt2^.rt^.elem) else writeln('Right: nil');
  if ukt2^.lf <> nil then P3(ukt2^.lf);
  if ukt2^.rt <> nil then P3(ukt2^.rt);
end;
 
 
var
  uktree1: t;
  c: integer;
 
begin
  assign(input, 'vh.txt');
  reset(input);
  assign(output, 'ou.txt');
  rewrite(output);
  while not eoln do
  begin
    read(c);
    P1(uktree1, c);
  end;
  writeln('***OBHOD***');
  P3(uktree1);
  writeln('***HEIGHT***');
  P2(uktree1);
  close(input);
  close(output);
end.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.11.2017, 19:27
Ответы с готовыми решениями:

Поиск повторов с помощью двоичного дерева.
Здравствуйте, Уважаемые Форумчане! Возник вопрос: Начал писать прогу по деревьям , вот сам код: ...

Разработать процедуру исключения вершины из двоичного дерева
Нужно срочное решени задач, кто решит буду очень признателен и благодарен... Решать все не нужно,...

Сортировка файла с помощью двоичного дерева поиска
На вход подается не отсортированный файл. На выходе имеем отсортированный файл, справа от каждой...

Разработайте процедуру исключения вершины из двоичного дерева
Разработайте процедуру исключения вершины из двоичного дерева

1
3837 / 1798 / 1974
Регистрация: 10.12.2014
Сообщений: 6,992
13.11.2017, 10:06 2
Для построения сбалансированного дерева, самый простой способ это АА-дерево.
(АА-дерево)
Этот способ гораздо проще, чем AVL и красно-чёрное дерево.
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
type
  pNode = ^tNode;
  tNode = record
    Left, Right : pNode;
    Level : Integer; 
    Key   : Integer;
  end;
 
{ выяснить, имеется ли данное значение в дереве }
function inTree(p : pNode; Key : Integer) : Boolean;
begin
  if p = nil then
    inTree := False
  else if p^.Key = Key then
    inTree := True
  else if p^.Key > Key then
    inTree := inTree(p^.Left, Key)
  else
    inTree := inTree(p^.Right, Key);
end;
 
{ поменять местами содержимое записей }
procedure Swap(p1, p2 : pNode);
var tmp : tNode;
begin
  tmp := p1^; p1^ := p2^; p2^ := tmp;
end;
 
{ устранение левой связи на одном уровне }
procedure Skew(t : pNode);
var l : pNode;
begin
  l := t^.Left;
  if (l <> nil) and (t^.Level = l^.Level) then
    begin
      Swap(t, l);
      l^.Left := t^.Right;
      t^.Right := l;
    end;
end;
 
{ устранение двух правых связей на одном уровне }
procedure Split(t : pNode);
var r : pNode;
begin
  r := t^.Right;
  if (r <> nil) and (r^.Right <> nil) and (t^.Level = r^.Right^.Level) then
    begin
      Swap(t, r);
      r^.Right := t^.Left;
      t^.Left := r;
      inc(t^.Level);
    end;
end;
 
{ Добавление нового узла в дерево }
procedure NodeInsert(var p : pNode; newKey : Integer);
begin
  if p = nil then
    begin
      New(P);
      p^.Left := nil; p^.Right := nil;
      p^.Level := 1; p^.Key := newKey;
    end
  else
    begin
      if newKey < p^.Key then NodeInsert(p^.Left, newKey)
      else if newKey > p^.Key then NodeInsert(p^.Right, newKey)
      else Exit;
      { Выполнить балансировку для каждой из вершин в данной ветке }
      Skew(p);
      Split(p);
    end;
end;
 
procedure Bypass(p : pNode);
begin
  Write('Node key :', p^.Key:3);
  Write('     Left :'); if p^.Left  <> nil then Write(p^.Left^ .Key:3) else Write('nil');
  Write('    Right :'); if p^.Right <> nil then Write(p^.Right^.Key:3) else Write('nil');
  WriteLn;
  if p^.Left  <> nil then Bypass(p^.Left );
  if p^.Right <> nil then Bypass(p^.Right);
end;
 
function heightTree(p : pNode) : Integer;
var l, r : Integer;
begin
  if p^.Left  <> nil then l := heightTree(p^.Left ) else l := -1;
  if p^.Right <> nil then r := heightTree(p^.Right) else r := -1;
  if l > r then heightTree := l + 1 else heightTree := r + 1;
end;
 
var
  root : pNode;
  txt : Text;
  Key : Integer;
 
begin
  Assign(txt, 'vh.txt');
  Reset(txt);
  
  { корень }
  Read(txt, Key);
  New(root);
  root^.Left := nil; root^.Right := nil;
  root^.Level := 1; root^.Key := Key;
 
  { Добавляем остальные элементы }
  while Not EOF(txt) do
    begin
      Read(txt, Key);
      NodeInsert(root, Key);
    end;
  Close(txt);
 
  { Обход }
  Bypass(root);
  WriteLn('Height = ', heightTree(root));
end.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.11.2017, 10:06

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Написать подпрограмму прямого обхода двоичного дерева
Написать подпрограмму прямого обхода двоичного дерева.

Напишите подпрограмму, которая вычисляет высоту двоичного дерева
Напишите подпрограмму, которая вычисляет высоту двоичного дерева турбо паскаль

Построение идеально сбалансированного двоичного дерева с заданным числом вершин
Построение и обход идеально сбалансированных двоичных деревьев. Реализовать программу, выполняющую...

Напишите программу, которая выводит на экран все узлы, находящиеся на заданном уровне двоичного дерева
Напишите программу, которая выводит на экран все узлы, находящиеся на заданном уровне двоичного...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.