Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.64/33: Рейтинг темы: голосов - 33, средняя оценка - 4.64
2 / 2 / 0
Регистрация: 16.10.2009
Сообщений: 65
1

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

14.12.2009, 23:56. Просмотров 6073. Ответов 4
Метки нет (Все метки)

Помогите с этой задачей)

Определить количество узлов на каждом уровне данного бинарного дерева.
Плиз помогите!!!!! если мона с коментариями каждой строки!!!!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
14.12.2009, 23:56
Ответы с готовыми решениями:

Бинарные деревья. Найти количество узлов на n уровне
Коротко о программе. Дано бинарное дерево. Нужно нерекурсивно(через стеки) найти количество узлов...

Определить количество вершин на к-уровне дерева
Дан указатель на корень дерева и натуральное число К. Определить количество вершин на к-уровне....

Определить количество листьев на каждом уровне дерева итеративным способом
Здравствуйте, необходима помощь. Необходимо написать процедуру, определяющую количество листьев на...

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

4
1063 / 130 / 34
Регистрация: 09.10.2009
Сообщений: 271
23.12.2009, 13:25 2
долго писать. кажется это надо еще вместе с деревом список (например, стек или даже 2 стека) использовать.
что-то вроде:
взять корень, положить в стек1.
повторить
затем в цикле пока стек1 не пуст -
вынуть очередной элемент, увеличить кол-во на очередном уровне, положить его во 2 стек.
пока стек2 не пуст
вынуть из него очреденой элемент, положить в стек1 правого и левого сына этого эл-та.
напечатать кол-во элементов на текущем уровне.
увеличить уровень на 1, обнулить кол-во эл-тов на переходе к следующему уровню.
пока стек1 не будет пуст ;
0
2 / 2 / 0
Регистрация: 16.10.2009
Сообщений: 65
23.12.2009, 21:13  [ТС] 3
Цитата Сообщение от Dnnn Посмотреть сообщение
долго писать. кажется это надо еще вместе с деревом список (например, стек или даже 2 стека) использовать.
что-то вроде:
взять корень, положить в стек1.
повторить
затем в цикле пока стек1 не пуст -
вынуть очередной элемент, увеличить кол-во на очередном уровне, положить его во 2 стек.
пока стек2 не пуст
вынуть из него очреденой элемент, положить в стек1 правого и левого сына этого эл-та.
напечатать кол-во элементов на текущем уровне.
увеличить уровень на 1, обнулить кол-во эл-тов на переходе к следующему уровню.
пока стек1 не будет пуст ;
вот типо того!!!!!!!!!!! ПОМОГИТЕ РЕШИТЬ ПЛИЗ!!!!!!!!!!!!!!
0
1063 / 130 / 34
Регистрация: 09.10.2009
Сообщений: 271
24.12.2009, 10:43 4
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
program B_Tree;
type PTree = ^ TTree; {Tip- ukazatel na element dereva}
     TTree = record el: integer; {tip el-ta dereva}
                    left, right: PTree; {ukazateli na lev i prav.sina}
             end;
 
     { type el-tov steka - informacija - eto ukazatel na el-t dereva, pred - uk-l na predidush. el-t }
     PStek= ^TStek;
     TStek= record Inf:  PTree;
                   pred: PStek;
             end;
 
 
var  Tree {ukaz. na koren dereva}, p, pr: PTree;
     elTree: integer;
 
     i,j: integer;
     c: char;
 
 {===================Stack ================================================}
 procedure InitStek(var top: PStek); { инициализация стека }
 begin top := nil;
 end;
 
 {proverka Steka na pustoty. true esli pusto }
 function PustStek(top: PStek): boolean;  
 begin PustStek := top = nil;
 end;
 
 procedure InStek(el: Ptree;  var top: PStek ); { добавление в стек эл-та со значением el }
 var p: PStek ;
 begin new(p); { выделили память под новый элемент }
       p^.inf := el;
       p^.pred := top; { указатель на предыдущий элемент берем из указателя на посл элемент стека }
       top := p; { теперь новый элемент стал посл. элементом стека, на него и будет указывать top}
  end;
 
  procedure OutStek(var el: PTree;  var top: PStek); {убираем из непустого стека посл элемент}
  var p: PStek;
  begin el := top^.inf; { запомнили значение эл-та }
        p  := top;     { запомнили ссылку на эл-т}
        top := top^.pred; {теперь уже ссылаемся на предпоследний эл-т стека}
        dispose(p);   {освобождаем память, бывшую под удаляемым эл-том }
  end ;
 
 
{===============Be-derevo ===========================================}
 {ini******acija dereva } 
 procedure InitTree(var tree:PTree);
 begin 
   tree := nil;  
 end; 
 
 {proverka dereva na pustoty. true esli pusto }
 function PustTree(tree:PTree): boolean;  
 begin PustTree := tree = nil;  
 end; 
 
 {-------------------------------------------------------------------}
 {dobavlenie v derevo }
 procedure AddInTree(el: integer; var tree:PTree);
 var p, pr, t: PTree;
 begin new(t); t^.el := el; {sozdaem novii el-t dereva}
       t^.left := nil; t^.right := nil; {nov.el-t bydet listom dereva}
       p:= tree; pr:=nil;
       {ishem mesto privjazki }
       while p<>nil do
       begin pr := p; {"predidushii" ukazatel}
 
             if p^.el > el then p:=P^.left
             else p:=p^.right;
       end;
       if tree = nil then tree := t {pervii uzel dereva}
       else if pr^.el>el then pr^.left := t
            else pr^.right := t;
 
 end;
 {--------------------------------------------------------------------}
 { Prjamoi obxod (pechat) dereva - uzel, levoe podderevo, pravoe podderevo - rekursuja }
 procedure PrintTree(tree: PTree);
 begin write(tree^.el, ' ');
       if tree^.left<>nil then PrintTree(tree^.left);
       if tree^.right<>nil then PrintTree(tree^.right);
 end;
 {------------------------------------------------------------------------}
 {Udalenie dereva}
 procedure ClearTree(var p:Ptree);
 begin if p^.left <> nil then ClearTree(p^.left);
       if p^.right <>nil then ClearTree(p^.right);
       dispose(p); p:=nil;
 end;
 
 { obxod dereva po urovnjam s pechatju kol-va el-tov na kazdom urovne }
 procedure ObxodPoUrovn(tree:Ptree);
 var elStek: PTree;
     top1, top2: PStek; { ukaz. na verchini vspomog. stackov }
     Uroven, Kol : integer;
 begin
 
     InitStek(top1); InitStek(top2);
 
     InStek(tree, top1); {взять корень, положить в стек1. }
 
     Uroven := 0;
 
     repeat {повторить }
 
       { увеличить уровень на 1, обнулить кол-во эл-тов на переходе к следующему уровню.}
       Kol := 0;
       Uroven := Uroven +1;
 
       writeln('Elementi ', Uroven,' yrovnja:');
 
 
       while not PustStek(top1) do {пока стек1 не пуст}
{ вынуть очередной элемент, увеличить кол-во на очередном уровне, положить его во 2 стек}
       begin OutStek(elStek, top1);
             kol := kol + 1;
             write(elStek^.el,' ');
             InStek(elStek, top2);
       end;
       writeln;
       writeln('Kol-vo elementov ', Uroven,' yrovnja:', kol);
 
       while not PustStek(top2) do {пока стек2 не пуст}
{ вынуть из него очередной элемент, положить в стек1 правого и левого сына этого эл-та.}
       begin OutStek(elStek, top2);
 
             if elStek^.right<>nil then
                    InStek(elStek^.right, top1);
 
             if elStek^.left<>nil then
                    InStek(elStek^.left,  top1);
       end;
 
     until PustStek(top1); {пока стек1 не будет пуст }
 end;
 
 {===================Osn programma ========================================}
begin
  InitTree(tree);
 
  writeln('Sozdanie dereva: ');
  repeat
    write('element dereva = ');
    readln(elTree);
    AddInTree(elTree, tree);
    write('Prodolzhit vvod (Y/N)?'); readln(c);
  until (c = 'N') or (c = 'n');
 
  if not PustTree(tree) then
  begin writeln('Obxod dereva (prjamoi):');
        PrintTree(tree);
 
        writeln;
        write('Nazmite ENTER...'); readln; 
 
        writeln('Podshet uzlov po urovnjam: ');
        ObxodPoUrovn(tree);
 
        ClearTree(tree);
  end;
  write('Nazmite ENTER...'); readln; 
end.
2
2 / 2 / 0
Регистрация: 16.10.2009
Сообщений: 65
28.12.2009, 19:51  [ТС] 5
Спасибо за задачу) но она мне чуть-чуть не подходит)

Добавлено через 1 минуту
Вот код:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
procedure CountLevel(level: integer; root: ttree;
          const to_count: integer; var Counter: integer);
begin
  if (root = nil) or (level > to_count) then exit;
 
  if level = to_count then inc(Counter)
  else begin
    CountLevel(level + 1, root^.right, to_print, Counter);
    CountLevel(level + 1, root^.left, to_print, Counter);
  end;
end;
, вот так вызывать:
  for i := 0 to Pred(GetHeight(root)) do begin
    amount := 0;
    CountLevel(0, root, i, amount);
    Writeln(i:2, ' -> ', amount);
  end;
мне подсказали, но не много) вот только кусочек) Помогите
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.12.2009, 19:51

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

Определить число узлов на каждом уровне дерева
Я не силен в деревьях, помогите пожалуйста

Количество узлов на каждом уровне
#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; typedef struct item { int data; struct item *left; ...

Подсчитать количество элементов на n-м уровне бинарного дерева
Помогите пожалуйста написать рекурсивную функцию или процедуру, которая подсчитывает количество...

Создание бинарного дерева и ограничение на количество узлов в ней
В задании по созданию бинарного дерева есть условие на то, что узлов в дереве должно быть не ...


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

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

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