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

Бинарные деревья. Найти количество узлов на n уровне

20.12.2013, 00:32. Просмотров 2759. Ответов 6
Метки нет (Все метки)

Коротко о программе.
Дано бинарное дерево. Нужно нерекурсивно(через стеки) найти количество узлов на n-ом уровне дерева.
В принципе алгоритм понятен. Имеется два стека. Сначала в 1 хранится корень дерева. Потом вытаскиваем из 1 стека корень и записываем два его поддерева в 2 стек. Далее в 1 стек каждое поддерево поддеревьев из 2 стека и так далее, пока не дойдем до n уровня, конечно, делая проверки на пустоту узлов и другие условия.

Вот код, написанный мной:
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
type tree = ^ukaz;
     ukaz = record 
              data: integer;
              left,right: tree;
            end;
     stack = ^stek;
     stek = record
              inf: tree;
              next: stack;
            end;
var x,n:integer;
    T:tree;             
{Процедура загоняет элемент в стек}
procedure inStack(var s:stack; el:tree);
var temp:stack;
begin
  new(temp); 
  temp^.inf:=el;
  temp^.next:=nil;
  if (s=nil) then 
  begin 
    s:=temp; 
  end else 
  begin 
    temp^.next:=s; 
    s:=temp; 
  end;
end;
{Процедура записывает элемент из стека в переменную}
procedure outStack(var s:stack; var el:tree);
var temp:stack;
begin
  if (s=nil) then el:=nil
  else begin 
         temp:=s; s:=s^.next; el:=temp^.inf;
         dispose(temp);
       end;
end;
{Функция считает количество элементов в стеке}
function kolInStack(var s:stack):integer;
var temp:stack;
    k:integer;
begin
  new(temp);
  temp:=s;
  k:=0;
  while (temp<>nil) do begin
   temp:=temp^.next;
   k:=k+1;
  end;
  kolInStack:=k;
end;
{Функция считает количество узлов на n-уровне бинарного дерева}            
function KolUzlov(var T:tree; n:integer):integer;
var s1,s2:stack;
    temp,element:tree;
    i:integer;
begin
  new(temp);
  temp:=T;
  i:=1;
  new(s2);
  new(s1);
  if (T=nil) then KolUzlov:=0 else 
  begin
    inStack(s1,temp);
    if (n=1) then KolUzlov:=1;
  end;
  while (i<n) and ((s1<>nil) or (s2<>nil)) do begin
    while (s1<>nil) do begin
      outStack(s1,element);
      if (element^.left<>nil) then inStack(s2,element^.left);
      if (element^.right<>nil) then inStack(s2,element^.right);
    end;
    while (s2<>nil) and (i<n) do begin
      outStack(s2,element);
      if (element^.left<>nil) then inStack(s1,element^.left);
      if (element^.right<>nil) then inStack(s1,element^.right);
    end;
    if (i<n) then i:=i+1 else i:=i+2;
  end;
  if (s1<>nil) then kolUzlov:=kolInStack(s1);
  if (s2<>nil) then kolUzlov:=kolInStack(s1);
end;
{Процедура формирует бинарное дерево}
procedure enter(var T:tree; x:integer);
begin
  if (T=nil) then 
  begin
    new(T);
    T^.data:=x;
    T^.right:=nil;
    T^.left:=nil;
  end else
    if (T^.data=x) then write('уже есть') else
      if (T^.data>x) then enter(T^.left,x) else 
        enter(T^.right,x);
end;
{Основная программа}
begin
  writeln('Введите элементы дерева. 0-конец ввода '); 
  read(x);
  while (x<>0) do begin
    enter(T,x);
    read(x);
  end;
  write('Введите уровень, на котором будете считать количество узлов дерева: ');
  readln(n);
  writeln(KolUzlov(T,n));
end.
Проблема заключается в том, что выскакивает ошибка на 72 строке:
Pascal
1
if (element^.left<>nil) then inStack(s2,element^.left);
Pascal
1
Derevo.pas(72) : Ошибка времени выполнения: Ссылка на объект не указывает на экземпляр объекта.
Понятия не имею как исправить. Буду признателен за помощь.
1
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.12.2013, 00:32
Ответы с готовыми решениями:

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

Бинарные деревья: найти максимальный элемент на каждом уровне
Задание: найти максимальный элемент на каждом уровне. Вывести эти значения Код: unit Unit1; ...

Бинарные деревья: создание, отображение, поиск узлов
Написать программу, которая выполняет следующие действия: 1. Генерирует с помощью генератора...

Бинарные деревья. Вывод потомков для каждого из узлов бинарного дерева поиска
Здравствуйте, уважаемые форумчане! Продолжая изучать бинарные деревья, решил подумать о выгодности...

6
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
30335 / 19827 / 7750
Регистрация: 22.10.2011
Сообщений: 34,575
Записей в блоге: 6
20.12.2013, 12:35 2
Замени свои строки вот на эти:
Pascal
62
63
s1 := nil;
s2 := nil;
, и эта ошибка перестанет возникать...
0
2 / 2 / 1
Регистрация: 29.06.2013
Сообщений: 42
20.12.2013, 17:47  [ТС] 3
Все бы хорошо, но теперь выводит неверное количество узлов. Блин
0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
30335 / 19827 / 7750
Регистрация: 22.10.2011
Сообщений: 34,575
Записей в блоге: 6
20.12.2013, 19:16 4
AslanVMK, я ошибаюсь или вот такая функция делает то, что тебе нужно?
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
{Функция считает количество узлов на n-уровне бинарного дерева}            
function KolUzlov(var T: tree; n: integer): integer;
var
  s: array[boolean] of stack;
  element: tree;
var
  odd_pass: boolean;
begin
  odd_pass := true; // первый проход - нечетный
  s[odd_pass] := nil;
  s[not odd_pass] := nil;
  
  if T = nil then KolUzlov := 0
  else if n = 1 then KolUzlov := 1
  else
  begin
    instack(s[odd_pass], T);
    repeat
      repeat
        outstack(s[odd_pass], element);
        if element <> nil then
        begin
          if element^.left <> nil then 
            instack(s[not odd_pass], element^.left);
          if element^.right <> nil then
            instack(s[not odd_pass], element^.right);
        end;
      until element = nil;
      dec(n); odd_pass := not odd_pass;
    until n = 1;
    KolUzlov := kolInStack(s[false]) + kolInStack(s[true]);
  end;
end;
1
2 / 2 / 1
Регистрация: 29.06.2013
Сообщений: 42
20.12.2013, 19:42  [ТС] 5
Все, работает. Не знаешь , почему у меня не работала?
0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
30335 / 19827 / 7750
Регистрация: 22.10.2011
Сообщений: 34,575
Записей в блоге: 6
20.12.2013, 19:45 6
Нет, мне проще было написать заново, чем разбираться в твоем коде...
0
2 / 2 / 1
Регистрация: 29.06.2013
Сообщений: 42
20.12.2013, 19:46  [ТС] 7
Ладно, разберусь уж дальше сам. Спасибо тебе)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.12.2013, 19:46

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

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

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

Деревья: количество листьев на заданном подуровне + удаление узлов
1.подсчитать кол-во листьев на заданном подуровне 2. удаление вершины с ее поддеревом через...

Бинарные деревья: Посчитать количество дедов в бинарном дереве
Функция выбрасывает исключение. Что здесь неправильно,и как написать правильно? int...


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

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

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