подсчет уровней в дереве

[Madmaxisss]

подсчет уровней в бинарном дереве

// в момент прохода kk:=1;
PROCEDURE  PRO_URO (tt :tree; kk :integer); 
begin
   if (tt^.pll<>nil) then 
      begin 
         inc(kk); 
         PRO_URO(tt^.pll,kk); 
      end;

   if (tt^.prr<>nil) then 
      begin 
         inc(kk); 
         PRO_URO(tt^.prr,kk); 
      end;

   write('>>',kk); // почему то не правильно, помогите плиз (должно выводить уровни по каждой ветке т.е. уровней kk  от tt до листка)
   kk:=1;

//pll - лево 
//prr - право
end;

[Stilet]

почему то не правильно

А как код себя ведет?

[Madmaxisss]

Сообщение от Stilet

А как код себя ведет?

                                 1
                       2                  2
                  3        3          3      3
                4   4               4  4

должно быть:
>>4>>4>>3>>4>>4>>3


а получается:
>>4>>5>>5>>4>>4>>5>>6>>6>>5>>5>>3

[Stilet]

должно быть:
>>4>>4>>3>>4>>4>>3

Как так? Не уловил логики

[Madmaxisss]

Сообщение от Stilet

Как так? Не уловил логики

от узла tt до листка N увеличиваем kk, как дошли до листка вывели kk, после чего kk:=1, и опять повторяем итерацию.

[grenles]

А кто сказал, что алгоритм считает уровни?
Как минимум

PROCEDURE  PRO_URO (tt :tree; kk :integer);

А для передачи параметра, надо

PROCEDURE  PRO_URO (tt :tree; VAR kk :integer);

Во-вторых.
Что у вас вообще считается? Сначала погружение влево до тупика, потом выход из рекурсии и погружение вправо через лево и так опять до тупика. Эдак вы просто посчитаете все узлы. но не уровни.

По логике еще вот что, Если вы влево уперлись в тупик - вы ничего не увидите, так как сразу погружаетесь вправо, и только из правого тупика вы выводите что-то. Тогда уж надо вывод делать после каждого тупик.

// в момент прохода kk:=1;
PROCEDURE  PRO_URO (tt :tree; var kk :integer); 
begin
   if (tt^.pll<>nil) then 
      begin 
         inc(kk); 
         PRO_URO(tt^.pll,kk); 
      end;


   write('>>',kk); // вывод при достижении левого тупика


   if (tt^.prr<>nil) then 
      begin 
         inc(kk); 
         PRO_URO(tt^.prr,kk); 
      end;

   write('>>',kk); // вывод при достижении правого тупика.)
   kk:=1; ??????? по логике это присвоение лишнее, Так как откат из рекурсии восстанавливает К на том уровне, на каком погрузились и это верно. Зачем его сбивать в 1?

//pll - лево 
//prr - право
end;

и еще для раздумий - у вас алгоритм идет ЛЕВО_ЛЕВО-ТУПИК-ПРАВ-ЛЕВО-ЛЕВО-ТУПИК-ПРАВО-ЛЕВО-ТУПИК...
Подумайте, что вы этим считаете.


И вот это не понял

должно быть:
>>4>>4>>3>>4>>4>>3


а получается:
>>4>>5>>5>>4>>4>>5>>6>>6>>5>>5>>3

Где в вашем дереве пятерка и почему начало с 4-ки?
я не вижу столько уровней

1
2 2
3 3 3 3
4 4 4 4

Как я читаю алгоритм 1-2-3 - тупик (3), выхода на 1-2-3-4 снова (4) - тупик, выход на 3: 1-2-3-4 (4), выход на уровень 1. Потом почти тоже самое. Жаль цифры одинаковые. ТО есть получится вывод:
4-4-3-4-4-3. При условии правильной передачи параметров и вывода в обоих местах. При вашем алгоритме вывод только после правого. Будет, без передачи параметров постоянно 1-1-1-1-1-1.


Мне видится так код правильнее

...
kk:=1;
....
PRO_URO (mytrre,kk);
.....

PROCEDURE  PRO_URO (tt :tree; var kk :integer); 
begin
   if (tt^.pll<>nil) then 
      begin 
         inc(kk); 
         PRO_URO(tt^.pll,kk); 
      end;

   write('>>',kk); // вывод при достижении левого тупика

   if (tt^.prr<>nil) then 
      begin 
         inc(kk); 
         PRO_URO(tt^.prr,kk); 
      end;

   write('>>',kk); // вывод при достижении правого тупика.)

end;

[eoln]

Без отладки трудно сказать (а код для построения дерева писать лень), но примерно такие изменения (ИМХО, конечно, могу ошибаться):
1) убрать inc(kk); - иначе в узлах где два листа дублироваться будет
2) вызов процедуры изменить на PRO_URO(tt^.pll,kk+1); и PRO_URO(tt^.prr,kk+1); соответственно.
3) write('>>',kk); делать после проверки if (tt^.pll=nil) and (tt^.prr=nil), т.е только в той итерации которая не порождает новую (то бишь в тупиковой ветви)

[Madmaxisss]

(сообщение eoln не заметил) а как тогда подсчитать уровни от узла(корня) tt в моем случае???

[grenles]

Сообщение от eoln

Без отладки трудно сказать (а код для построения дерева писать лень), но примерно такие изменения (ИМХО, конечно, могу ошибаться):
1) убрать inc(kk); - иначе в узлах где два листа дублироваться будет
2) вызов процедуры изменить на PRO_URO(tt^.pll,kk+1); и PRO_URO(tt^.prr,kk+1); соответственно.
3) write('>>',kk); делать после проверки if (tt^.pll=nil) and (tt^.prr=nil), т.е только в той итерации которая не порождает новую (то бишь в тупиковой ветви)

Смотря что он хочет посчитать. В предложенном вами варианте - будут считать только те узлы, у которых оба потомка пусты. При том варианте, как у него - считаются варианты, когда один из потомков пуст, то есть возможен "обратный" подстчет при откате, когда дерево постоено только в одну сторону - лево или право, и при возврате из рекурсии будут считаться "пустые НИЛЛЫ" - 4-3-2-1, до корня. Поэтому надо ему решить, что и как он считает.

Ваш вариант может быть более верный. Считать только самые крайние узлы.

Еще раз сформулируй конкретно задачу, что ты хочешь посчитать?

Дай точнее определение в твоем понятии - что такое уровень дерева. Условия его определения.

[Madmaxisss]

Сообщение от grenles

Еще раз сформулируй конкретно задачу, что ты хочешь посчитать?

Дай точнее определение в твоем понятии - что такое уровень дерева. Условия его определения.

по идее я упростил задачу))) ну вообще задача стоит следующая: делается обход дерева и от узла(корня) tt до ветки нужно занести в дерево значения kk (красным цветом).