Бинарное дерево рекурсивная задача

Question

Я обнаружил эту проблему, и я не очень уверен, что мой подход к подходу правильный:

"Бинарное дерево может быть закодировано с использованием двух функций l и r, таких что для узла n, l(n) дает левого дочернего элемента n (или nil, если его нет), а r (n) дает правого дочернего элемента (или nil, если его нет). Пусть Test (l, r, x) будет простым рекурсивным алгоритмом длябинарное дерево, закодированное функциями l и r, вместе с корневым узлом x для двоичного дерева, и возвращает «да», если ни у одного узла в дереве нет только одного дочернего элемента. Дайте псевдокод для этого алгоритма. "

Я пробовал это:

test(l,r,x)
  if((l(x)!=null && r(x)!=null) || (l(x)==null && r(x)==null)) 
     return "yes"
   else return "no"

  if(test(l,r,l(x))=="yes") test (l,r,l(x)) else return "no"
  if(test(l,r,r(x))=="yes") test (l,r,r(x)) else return "no"

 return "yes"

Это правильно?Если l и r являются функциями, почему они передаются как нормальные параметры при вызове функции?

Заранее благодарим вас за ваши ответы!

Answer 1

У вас есть три основных условия: оба потомка равны нулю, один потомок равен нулю или ни один из потомков не равен нулю. Я бы также проверил их в таком порядке (потому что это немного упрощает логику):

if l(x) == null && r(x) == null
    return true;
if l(x) == null || r(x) == null  // only need inclusive OR, due to previous test.
    return false;
return test(l, r, l(x)) && test(l, r, r(x))

Что касается передачи l и r в качестве параметров, все зависит от некоторых: некоторые языки (например, функциональные языки) позволяют передавать функцию в качестве параметра. Другие (например, C, C ++ и т. Д.) Вместо этого передают указатель на функцию - но это в значительной степени не имеет значения. Некоторые не позволят вам передать что-то вроде функции, и в этом случае вам придется встроить ее. В этом случае вы на самом деле не много получаете (что-нибудь?), Передавая l и r как параметры в любом случае. Передача функции в качестве параметра полезна, прежде всего, когда / если принимающая функция не знает, какую функцию она получит априори (что она делает здесь).

Answer 2

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

if((l(x)!=null && r(x)!=null) || (l(x)==null && r(x)==null)) 
    return "yes"
else return "no"

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

if this node has both children
    return the result of test(l,r,l(x)) && (test(l,r,r(x))
if this node has no children
    return true
if this node has 1 child
    return false

в соответствии с вашим последним вопросом («Если l и r являются функциями, почему они передаются как нормальные параметры при вызове функции?»), Ответ таков: они не имеют для передается в качестве параметров. Это просто обозначение, которое они выбрали, когда сказали: «Бинарное дерево может быть закодировано с использованием двух функций l и r [...]»

Answer 3

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

Я бы изменил это так, чтобы, если у вас был один ребенок, вы возвращали «нет», в противном случае вы возвращаете «да» или «нет» в зависимости от того, соответствуют ли ваши дети критериям.

test(l,r,x)
  if((l(x)!=null && r(x)==null) || (l(x)==null && r(x)!=null)) 
     return "no"
  if(l(x) == null && r(x) == null) 
    return "yes"
  return test(l,r,l(x)) && test(l,r,r(x))