% 6. Определить максимальное количество дочерних узлов в дереве.
% дерево = tr(<Значение узла>,<левая ветка>,<правая ветка>).

% запускать:
% tree_weight(<Дерево>,RES).

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

% Пример:
% tree_weight(tr(1,tr(1,tr(1,void,void),tr(1,void,void)),tr(1,tr(1,void,void),tr(1,void,void))),SHIRINA).

%% Находим максимальное значение из списка.
 
max_from_list([],RES):- RES=0. %максимальный элемент из пустого списка = 0
 
max_from_list([X|TAIL],RES) :-  %если первый элемент списка меньше максимума
  max_from_list(TAIL,RES1),     %из оставшевшегося списка - то максимум равен
  X<RES1,                       %максимуму из оставшегося списка (мы его уже знаем)
  !,                            %дальше не ищем, выводим результат
  RES=RES1.
 
max_from_list([X|_],RES) :-     %если не сработало предыдущее правило, то максимум
  RES=X.                        %равен первому элементу текущего списка
 
 
%сложить два списка поэлементно
 
add([],X,RES) :- RES=X.        %сложение списка с пустым = тот же список
 
add(X,[],RES) :- RES=X.        %сложение списка с пустым = тот же список
 
add([H1|T1],[H2|T2], RES) :- 
  T is H1+H2,                  %вычитаем сумму первых элементов и
  add(T1,T2,RES2),             %суммируем хвосты списков
  append([T],RES2,RES).        %добавляем в итоговый список сумму первых элементов
 
%создаёт из дерева список, который содержит количества узлов поуровнево
%то есть если дерево имеет высоту три, и заполненно всё, то список будет выглядеть
%[1,2,4,0]- на первом уровне 1 элемент - корень, на втором - два, на третьем - 4, 
%на четвертом - 0
 
tree_list(void,[0]).           %пустое дерево содержит 0 узлов на своём уровне 
 
tree_list(tr(_,L,R),D) :-      
  tree_list(L,T1),             %получаем список количества узлов левого дерева
  tree_list(R,T2),             %получаем список количества узлов правого дерева
  add(T1,T2,RES),              %суммируем списки поэлементно
  append([1],RES,D).           %добавляем единицу в начало списка (текущий корень)
 
 
%находим ширину дерева
tree_weight(Tree,RES):-       
  tree_list(Tree,List),        %получаем список количества узлов дерева поуровнево 
  max_from_list(List,RES).     %находим максимум из этого списка, он равен нашей ширине