Поменять местами поддеревья так,чтобы узлов в левом было

Программирование Помощь с решением задач на Prolog Обработка графов (деревьев) на Prolog Поменять местами поддеревья так,чтобы узлов в левом было

Помечено: , ,

В этой теме 1 ответ, 2 участника, последнее обновление 1 год, 4 мес. назад.

  • Автор
    Сообщения
  • #4776
    @necromancersergio

    Здравствуйте,дано задание(Arity Prolog): В каждом узле дерева поменять при необходимости поддеревья местами так, чтобы в результирующем дереве в каждом узле выполнялось требование – количество узлов в левом поддереве не больше, чем в правом. Аргументы: произвольное бинарное дерево; результирующее дерево.
    Пример решения

    ?- pred(s(f(b(m,k),a),t(a,g)),X). X = s(t(a,g),f(a,b(m,k))) 
    yes 

    Набросал нерабочий код,смысл которого заключается в том,что есть рабочие предикаты по подсчету узлов в дереве (count_nodes) и перестановки левых и правых поддеревьев во всем дереве (change_tree). Предполагается,что я посчитаю кол-во узлов в правом и левом поддереве,если в левом узлов больше,то меняем их местами и проводим проверку на уровень ниже. Если нет(узлов в левом => в правом),то просто переходим на уровень ниже.

    check(Tree,X):-
    	Tree=..[Head,Left,Right],
    	count_nodes(Left,Nodes_Left),count_nodes(Right,Nodes_Right),
    	Nodes_Left > Nodes_Right,
    	change_tree(Tree,Y),
    	Y=..[Head,Left,Right],
    	check(Left,Left_Result),check(Right,Right_Result),
    	X=..[Head,Left_Result,Right_Result].
    check(Tree,X):-
    	Tree=..[Head,Left,Right],
    	count_nodes(Left,Nodes_Left),count_nodes(Right,Nodes_Right),
    	Nodes_Left =< Nodes_Right,
    	check(Left,Left_Result),check(Right,Right_Result),
    	X=..[Head,Left_Result,Right_Result].
    count_nodes(Tree,Nodes):-
    	Tree=..[_,Left,Right],
    	count_nodes(Left,Nodes_Left),
    	count_nodes(Right,Nodes_Right),
    	Nodes is Nodes_Left+Nodes_Right+1.
    count_nodes(Tree,1):-atomic(Tree).
    change_tree(Tree,Res):-
    	Tree=..[Head,Left,Right],
    	change_tree(Left,Left_Result),
    	change_tree(R,Right_Result),
    	Res=..[N,Right_Result,Left_Result].
    change_tree(Tree,Tree):-atomic(Tree).

    Помогите довести программу до ума.

  • #4785
    @admin

    Не понял что по вашему замыслу делает предикат check, но код должен выглядеть примерно так:

    change_tree(Tree, Res):-
      Tree=..[Head, Left, Right],
      change_tree(Left, Left_Result),
      change_tree(Right, Right_Result),
      count_nodes(Left, LeftCount),
      count_nodes(Right, RightCount), (
        LeftCount =< RightCount, !,
        Res=..[Head,Left_Result, Right_Result];
        Res=..[Head, Right_Result, Left_Result]
      ).
    change_tree(Tree, Tree):-
      atomic(Tree).

    Из того, что написано у вас тут используется только count_nodes. Результат выполнения приведен на скриншоте.

Для ответа в этой теме необходимо авторизоваться.