Подсчёт количества вершин у двоичного дерева

[Asya7]

Подскажите, пожалуйста! Как можно осуществить и как ответ оформить?2) Посчитать разность для каждой вершины полученного дерева между количеством левых и правых поддеревьев. .Что на выходе должно быть?(ведь может быть огромное количество вершин в дереве). У меня была такая задача:1) Построить двоичное дерево сортировки. - вроде её получилось сделать( не знаю на сколько правильно, но вроде работает) И относительно её хотелось бы вторую сделать. Так можно наверное?

program z_1;

type
   pTree = ^Tree;
   Tree = record
      name: integer;
      left: pTree;
      right: pTree
   end;

var
   s: integer;
   t: pTree;
   n, i: integer;

procedure insert(var T: pTree; x: integer);
begin
   if T = nil then begin
      new(T);
      T^.name := x;
      T^.left := nil;
      T^.right := nil;
   end
   else  if T^.name >= x then
      insert(t^.left, x)  
   else insert(t^.right, x);
end;

procedure obhod(t: Ptree);
begin
   if T <> nil then begin
      obhod(T^.left);
      write(t^.name,',');
      obhod(t^.right);
   end;
end;

begin
   write('kol-vo chisel: ');
   read(n);
   t := nil;
   for i := 1 to n do 
   begin
      read(s);
      insert(t, s);
   end;
   write('result. sortirovki: ');
   obhod(t);
   readln;
end.

[GreenWizard]

уговорили, отвечу я, коль остальные молчат :-D
Оформить ответ я не знаю как, но реализовал бы два варианта: вывод для каждой вершины и вывод только для корневого узла.... а там уже пусть препод выбирает, благо что почти тот же код и можно тупо скопировать код одного варианта и допилить до второго)
Про реализацию: фактически, за основу бери код obhod-a.... новая ф-ия должна возвращать количество вершин указанного узла т. е. если вызвали для корня - вернёт общее число узлов дерева, если вызвали для левого/правого узла - вернёт общее число узлов левого/правого поддерева, если вызвали на nil - вернёт 0.... думаю, что сможешь реализовать, там та же рекурсия, что и в obhod)
Главное отличие при выводе ответа: если мы считаем только разность левого и правого узла корня, то всё как выше написал, без особых заморочек..... если вывод для каждого узла, то просто в нашей новой функции сохраняем к-во узлов лево/право, выводим разницу, а потом просто возвращаем сумму лево/право..... отличие лишь в наличие вывода, а так-то тот же код

[Asya7]

GreenWizard, спасибо за объяснения! Буду пробовать реализовать.

[GreenWizard]

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

GreenWizard, спасибо за объяснения! Буду пробовать реализовать.

если что, пиши в ВК или Асю, помогу с кодом

[Asya7]

Только сейчас что-то получилось, но это не совсем то.. Помогите, если может кто. Пожалуйста!

(*6) Посчитать разность для каждой вершины полученного дерева
 между количеством левых и правых поддеревьев.*)
program z_5;

type
   pTree = ^Tree;
   Tree = record
      name: integer;
      left: pTree;
      right: pTree;
   end;

var
   a, r, l, k, s: integer;
   t: pTree;


procedure insert(var T: pTree; x: integer);
begin
   if T = nil then begin
      new(T);
      T^.name := x;
      T^.left := nil;
      T^.right := nil;
   end
   else  if T^.name >= x then
      insert(t^.left, x)  
   else insert(t^.right, x);
   
end;

procedure obhod(t: Ptree);
begin
   if T <> nil then begin
      obhod(T^.left);
      write(t^.name, ',');
      obhod(t^.right);
   end;
end;

procedure postorder(p: ptree; g: integer);
begin
   if p^.left <> nil then postorder(p^.left, k + 1);
   k := k + 1;
   if p^.right <> nil then postorder(p^.right, k + 1);
end;

procedure LV(p: ptree; g: integer);
begin
   if p^.left <> nil then LV(p^.left, l + 1);
   l := l + 1;
   if p^.right <> nil then LV(p^.right, l + 1);   
end;

procedure RV(p: ptree; g: integer);
begin
   if p^.left <> nil then RV(p^.left, r + 1);
   r := r + 1;
   if p^.right <> nil then RV(p^.right, r + 1);
end;


begin
   a := 0;
   write('vvedi chisla: ');
   repeat 
      read(s);
      insert(t, s);
   until s = 112;
   write('result. sortirovki: ');  
   obhod(t);  
   writeln;
   if (t^.right <> nil) or (t^.left <> nil) then
      postorder(t, a);
   if t^.left <> nil then LV(t^.left, a);
   if t^.right <> nil then RV(t^.right, a);
   
   writeln('vsego vershin:', k); 
   writeln('right vershin:', r);
   writeln('left vershin:', l);
   writeln('difference:', abs(l - r));
   readln;
end.

Если можно, то объясните, а как можно найти количество вершин для какого-нибудь элемента в дереве( я не совсем понимаю, они вроде никак не пронумерованы конкретно. Или это через цикл делается - вычитая из кол-ва всех элементов и дойдя до нужного... -ПОЯСНИТЕ, ЕСЛИ ЗНАЕТЕ. .. и эта нумерация - связана ли со способом обхода дерева?) Точно! Вот ещё: был такой момент: после написания команды вывода в самой процедуре (получилось случайно) , то вывелись разные цифры - так это наверное и есть вершины для каждого поддерева?? Или это не то? Ну в общем вывести для каждого - совсем не получается.. Подскажите как?(

[GreenWizard]

1) случайные т. к. нужно не полагаться на компилятор, а в начале работы присвоить им 0
2) особого порядка нет.... это.похоже на организацию некой фирмы: есть глава и от 0 до 2 замов, а у них от 0 до 2 помошников.... нужно просто посчитать количество подчинённых у узла/человека
3) умница, конечно, что сделала на глобальных переменных, но перепиши на одну функцию... будет намного проще и меньше кода

[Asya7]

Всё понятно! Да, я переделаю - в одну функцию. Огромное спасибо!

[GreenWizard]

   if t^.left <> nil then LV(t^.left, a);
   if t^.right <> nil then RV(t^.right, a);
   
   writeln('vsego vershin:', k); 
   writeln('right vershin:', r);
   writeln('left vershin:', l);
   writeln('difference:', abs(l - r));

должно стать:

   l := countNodes(t^.left);
   r := countNodes(t^.right);
   
   writeln('vsego vershin:', l + r + 1); 
   writeln('right vershin:', r);
   writeln('left vershin:', l);
   writeln('difference:', abs(l - r));

хотя я бы ещё проверял не nil ли t + abs тут не нужно т. к. тогда не понять куда дерево "перекошено"

[Asya7]

Уже всё переделано как нужно - спасибо Вам!