Как найти глубину двоичного дерева с помощью Prolog

Я изучаю Пролог и пытаюсь найти глубину двоичного дерева с помощью Пролога. Я представляю такое дерево:

nil is a tree.
tree(1,nil,nil) this is a leaf.
tree(1,tree(1,nil,nil),nil) this is a tree with root 1 and has a left leaf 1.

Мне нужен предикат глубины для этой глубины (T, N), который будет истинным, если N - глубина дерева T. Я предполагаю, что я буду использовать предикат глубины, когда T не является переменной, но N может быть переменной. Примеры:

?- depth(nil,N).
N = 0.

?- depth(tree(1,tree(2,nil,tree(3,nil,nil)),tree(5,tree(6,nil,nil),nil)),N).
N = 3.

?- depth(tree(1,nil,tree(2,nil,nil)),N).
N = 2.

Я не уверен, как это сделать, чтобы N было максимумом между двумя поддеревьями.

Спасибо за любую помощь.

Решение:

depth(nil,0).
depth(tree(_,nil,nil),1).
depth(tree(_,Left,Right), D) :- 
    depth(Left,DLeft),
    depth(Right,DRight),
    D is max(DLeft, DRight) + 1.

prolog
person user550413    schedule 22.01.2011    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Просто как пирог: глубина nil равна 0:

depth(nil,0).

В случае tree рекурсивно вызовите depth/2 в обеих ветвях и max их:

depth(Left,DLeft),
depth(Right,DRight),
D is max(DLeft, DRight) + 1.
person Fred Foo    schedule 22.01.2011
comment
Я получаю следующее ОШИБКА: ОШИБКА: = ‹/ 2: Арифметика:« глубина / 1 »не является функцией. ИЗМЕНЕНО ВЫШЕ. - person user550413; 22.01.2011
comment
Дай угадаю, ты, наверное, звонишь max(depth(L), depth(R))? Это не сработает. Вызовите depth дважды, чтобы получить значения, затем max их в следующей строке. - person Fred Foo; 22.01.2011
comment
Вы не можете использовать определяемый пользователем предикат в is/2, по крайней мере, с дополнительным (непереносимым) кодом. Просто вызовите предикат дважды. - person Fred Foo; 22.01.2011
comment
Большое спасибо, теперь он работает. Я новичок в Prolog, поэтому следующие вопросы будут звучать глупо, но: 1) Почему я не могу использовать определяемый пользователем предикат? 2) max - это встроенная функция / предикат? 3) Когда вы говорите "/ 2", что это значит, я считаю, что это поможет мне лучше понять ошибки. - person user550413; 22.01.2011
comment
1) Вы просто не можете. Некоторые прологи позволяют это, но стандартный пролог ISO этого не делает, IIRC. 2) Да. 3) is/2 - это инфиксный предикат is для арифметической оценки. Он принимает два аргумента (левую и правую), следовательно, /2. - person Fred Foo; 22.01.2011