Форум программистов, компьютерный форум, киберфорум
Delphi для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.67/15: Рейтинг темы: голосов - 15, средняя оценка - 4.67
0 / 0 / 0
Регистрация: 21.11.2015
Сообщений: 27
1

Вывести номера уровней данного бинарного дерева, на которых имеются листья

30.01.2016, 09:59. Показов 2830. Ответов 5
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Вывести номера уровней данного бинарного дерева, на которых имеются листья

Помогите понять суть задания. Листья же вроде имеются на всех уровнях, кроме последних
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.01.2016, 09:59
Ответы с готовыми решениями:

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

Как вывести все листья бинарного дерева?
имеется Б-дерево. Как вывести все листья? class B_tree { public: B_tree(); B_tree(int...

Вывести на экран номера строк матрицы, в которых имеются положительные элементы
помогите пожалуйста, я начинающий программист и что то пока не очень выходит. мне надо решить две...

Определить количество узлов на каждом уровне данного бинарного дерева
Помогите с этой задачей) Определить количество узлов на каждом уровне данного бинарного дерева....

5
5784 / 4526 / 1431
Регистрация: 14.04.2014
Сообщений: 20,157
Записей в блоге: 20
30.01.2016, 14:34 2
лист - это узел, из которого ничего не растет
в теории, может быть на любом уровне
0
0 / 0 / 0
Регистрация: 21.11.2015
Сообщений: 27
03.02.2016, 10:44  [ТС] 3
А может вы знаете, как посчитать и вывести эти уровни? Вот код
Delphi
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
121
122
unit Unit1;
 
interface
 
uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Buttons, StdCtrls, ExtCtrls;
 
type
  TForm1 = class(TForm)
    Button1: TButton;
    BitBtn1: TBitBtn;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Label4: TLabel;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;
 
Type
  Tkey = integer;
  Ttree=^ Tree;
  Tree = record
    Key: Tkey;
    Left: Ttree;
    Right: TTree;
  end;
 
var
  Form1: TForm1;
   t: Ttree;
implementation
 
{$R *.dfm}
 
Procedure make(Var work:Ttree; x:tkey);
Begin
  New(Work);
  Work^.Key:=x;
  Work.Left:=nil;
  Work.Right:=nil;
end;
 
Procedure insert(Work:TTree; x:Tkey);
Var
  Work2:tTree;
begin
  While work <> nil do
  begin
    Work2:=work;
    if x < work^.key then
      work:=work^.left
    else
      work:=work^.right;
   end;
   Work:=Work2;
  make(Work2,x);
  If (x < work^.key) then
    work^.left:=work2
  else
    work^.right:=work2;
end;
 
Procedure Vvod(var tree: ttree);
var
  Fin: textfile;
  x: tkey;
begin
  assignfile(fin,'Insert.txt');
  reset(fin);
  readln(fin,x);
  make(tree,x);
  while not eof(fin) do
  begin
    readln(fin,x);
    insert(tree,x);
  end;
  closefile(fin);
end;
 
Procedure preOrder(Work:TTree;Var str:string);
begin
  if (Work<>nil) then
  begin
    Preorder(work^.right,str);
    Preorder(work^.left,str);
    str:=str+ inttostr(work^.key)+' ';
  end;
end;
 
Procedure Podschet(Work:TTree;Var s:string);
var
  k:integer;
begin
  k:=0;
  if (Work<>nil) then
  begin
    Podschet(work^.right,s);
    Podschet(work^.left,s);
    if (work^.right = nil) and (work^.left=nil) then
      s:=s+ inttostr(work^.key)+' ';
  end;
end;
 
 
procedure TForm1.Button1Click(Sender: TObject);
Var
  S:string;
  Str: string;
begin
 Vvod(t);
 Preorder(t,s);
 Podschet(t,str);
 label4.Caption:=s;
 label2.Caption:=str;
end;
 
end.
0
5784 / 4526 / 1431
Регистрация: 14.04.2014
Сообщений: 20,157
Записей в блоге: 20
03.02.2016, 13:10 4
во-первых, с точки зрения соглашений Delphi по языку:
Delphi
1
2
3
4
5
6
7
8
Type
  Tkey = integer;
  PNode=^TNode;
  TNode = record
    Key: Tkey;
    Left: TNode;
    Right: TNode;
  end;
во-вторых, вместо передачи указателя проще пользоваться var Node:TNode, чтобы не писать все время ^

далее, можно передать в процедуру podschet еще один параметр level
и вместо накопительной строки воспользоваться например TList
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
procedure GetLeavesLevels(var Node:TNode; L:TList; level:integer);
begin
  if (node=nil) then exit;
 
  Podschet(Node.right,s, level+1);
  Podschet(Node.left,s, level+1);
 
  if (Node.right = nil) and (Node.left=nil) then
    if l.indexOf(pointer(level))=-1 then
      l.add(pointer(level)); 
end;
 
...
L:=Tlist.Create;
s:='';
GetLeavesLevels(t, L, 0);
// сейчас  в TList - список уровней всех узлов, не имеющих подузлов
// сформируем из него строку
for i:=0 to L.Count-1 do
begin
  s:=s+inttostr(integer(L[i]))+' ';
end;
l.free;
showMessage(s);
Добавлено через 21 минуту
уточню - тут получается список уровней самих листьев
список уровней, которые имеют листья - все на единицу меньше
1
0 / 0 / 0
Регистрация: 21.11.2015
Сообщений: 27
05.02.2016, 09:58  [ТС] 5
А вы не могли бы объяснить, что вот это делает?
Delphi
1
2
if l.indexOf(pointer(level))=-1 then
      l.add(pointer(level));
0
5784 / 4526 / 1431
Регистрация: 14.04.2014
Сообщений: 20,157
Записей в блоге: 20
05.02.2016, 10:11 6
TList - это список указателей (pointer)
а у нас level:integer;
но т.к. pointer и integer - оба 4-байтные целые числа, их типы можно "приводить" друг к другу
т.е. число 1 так и останется числом 1 но компилятор будет уже думать что это pointer

l.indexOf - поиск указателя в списке. если нашел, выдает индекс, если нет - минус единицу

таким образом здесь просто написано
если Level еще нет в списке, то добавить

В старших версиях делфи можно написать L:TList<integer>
тогда все проще:
Delphi
1
2
if L.indexOf(Level)=-1 then
  L.add(level);
0
05.02.2016, 10:11
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.02.2016, 10:11
Помогаю со студенческими работами здесь

Для каждого бинарного дерева выполнить преобразование дерева в список, результат вывести в виде списка списков
Объясните почему не работает, задание было таким &quot; Дан список, элементы которого — непустые...

Найти номера двух соседних чисел из данного набора, произведение которых является минимальным, и вывести вначале меньший, а затем больший номер.
1) Дано целое число N (&gt;1) и набор из N чисел. Найти номера двух соседних чисел из данного набора,...

Определить число узлов дерева, у которых имеются 2 потомка
a. Определить число узлов дерева, у которых имеются 2 потомка. b. Определить есть ли узел с данным...

Выборка данных с различных уровней дерева по id категории из середины дерева
Здравствуйте. Такая штука: есть дерево категорий, известен Id категории, которая находится в...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru