Блог

Предполагается, что моя программа prolog берет двоичное дерево и создает новое дерево, которое добавляет дочерний элемент к любому узлу, у которого есть только один дочерний элемент, так что у всех узлов есть 2 или ноль дочерних элементов. Используемое представление двоичного дерева выглядит следующим образом: t(73,t(31, t (5, nil, nil), nil), t(101,t(83, nil, t(97, nil, nil)), nil)). Проблема в том, что это исправляет только узлы, у которых отсутствует правый дочерний элемент, и не работает для узлов, у которых отсутствует левый узел.

 treeEx(X) :-
    X = t(73,t(31,t(5,nil,nil),nil),t(101,t(83,nil,t(97,nil,nil)),nil)).

singleFill(t(_,nil,nil),_,_):-!.

singleFill(t(Root,nil,Right),V,t(Root,t(V,nil,nil),Right)):- 
    singleFill(Right,V,_).

singleFill(t(Root,Left,nil),V,t(Root,Left,t(V,nil,nil))):-
    singleFill(Left,V,_).

singleFill(t(Root,Left,Right),V,t(Root,LD,RD)):-
   singleFill(Left,V,LD),
   singleFill(Right,V,RD).
  

При использовании treeEx запроса(T),singleFill(T,0,L). это должно привести к результату:

 T = t(73, t(31, t(5, nil, nil), nil), t(101, t(83, nil, t(97,
nil, nil)), nil)),
L = t(73, t(31, t(5, nil, nil), t(0, nil, nil)), t(101, t(83,
t(0, nil, nil), t(97, nil, nil)), t(0, nil, nil))) 
  

однако мой выдает:

 T = t(73, t(31, t(5, nil, nil), nil), t(101, t(83, nil, t(97, nil, 
nil)), nil)),
L = t(73, t(31, t(5, nil, nil), t(0, nil, nil)), t(101, t(83, nil, 
t(97, nil, nil)), t(0, nil, nil))) .
  

Проблема в том, что узел с 83 имеет одного дочернего элемента, но он не добавляет ноль. Когда я проследил это, я заметил, что это потому, что есть 2 отдельных вызова reclusive, которые имеют 2 разные формы дерева, поэтому я думаю, что только узлы с правильными дочерними элементами сохраняют изменения в новом дереве. Однако изменения в левом дереве не

Итак, сразу же у нас есть несколько странных вещей о вашем коде:

 ?- singleFill(t(1,nil,nil), 0, Y).
true.
  

Для меня странно, что это правда, но ничего не привязывало Y . Это должно быть поведение, которое вы заметили. Я думаю, это может быть связано с этим:

 ?- singleFill(nil, 0, Y).
false.
  

А именно, ваш код не обрабатывает базовый вариант рекурсии. Вот почему вам, похоже, нужно так много случаев. Всегда проверяйте свои предикаты с простыми входными данными, близкими к базовым случаям, это те, которые помогут вам увидеть проблему. На самом деле вам нужно всего три случая:

 single_fill(nil, New, t(New, nil, nil)).
single_fill(t(V, nil, nil), _, t(V, nil, nil)) :- !.
single_fill(t(V, Left, Right), New, t(V, NewLeft, NewRight)) :-
    single_fill(Left, New, NewLeft),
    single_fill(Right, New, NewRight).
  

Обратите внимание, что здесь я игнорирую только одну переменную, и это переменная заполнения в случае, когда заполнение не происходит.

У меня все еще есть сокращение, которое меня не устраивает. Без сокращения первое решение соответствует вашей спецификации, но вы получаете еще несколько, в основном по одному для каждого случая, когда в обеих ветвях дерева было nil. При вырезании этот предикат успешно «проверит» эти входные данные, даже если он их не сгенерирует, что является нарушением обратной корректности. Это наводит меня на мысль, что может быть лучший способ написать это, в котором нет этой проблемы. Но я не мог об этом подумать. Я чувствую, что вместо этого должно быть достаточно сказать Left = nil, Right = nil , но это не сработало.