진 나무는 재귀 문제

Question

나는이 문제를 발견하고 나는 나의 접근 방식이 옳다면 아주 확실하지 않다 :

"A 이진 트리가 두 가지 기능의 L과 R을 사용하여 인코딩 될 수있는 노드 (0, 1)은 왼쪽 자식을 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" 

리터 r은 기능을하는 경우, 왜 함수가 호출 될 때 정상 매개 변수로 전달되는 것이 맞습니까??

는 귀하의 답변에 미리 감사합니다!

Answer 1

당신이 제일 먼저 마지막 부분에 연결할 수 있도록, 예 또는 아니오 반환 중 하나입니다.

자녀가 한 명이라면, 아니요, 그렇지 않으면 자녀가 기준을 충족하는지에 따라 예 또는 아니요를 반환하도록 변경합니다.

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)) 

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이 기능이 있다면, 왜이 함수가 호출 될 때 정상적인 매개 변수로 전달됩니다")는 대답은 그들이 에을 매개 변수로 전달하지 않는다는 것입니다. "2 진 트리는 두 개의 함수 l과 r [...]을 사용하여 인코딩 될 수 있습니다."라고 말한 표기법입니다.

Answer 3

세 가지 기본 조건이 있습니다. 두 자녀 모두 null이거나 하나의 자식이 null이거나 둘 다 아닙니다. 자식은 null입니다. (이 논리 조금 단순화 때문에) 나뿐만 아니라 그 순서대로 테스트 것 : l 및 매개 변수가 간다 r을 통과 마찬가지로 지금까지

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)) 

를, 모두는 따라 달라집니다 일부 언어 (예를 들어, 함수형 언어) 함수를 매개 변수로 전달할 수 있습니다. 기타 (예 : C, C++ 등) 대신 함수에 대한 포인터를 전달해야합니다. 그러나 이는별로 중요하지 않습니다. 어떤 함수는 함수처럼 넘겨주지 않습니다.이 경우에는 실제로 매개 변수로 l 및 r을 전달하여 실제로 많이 얻지는 못합니다. 함수를 매개 변수로 전달하는 것은 주로 수신 함수가 어떤 함수를 선험적으로 수신하는지 알 수없는 경우 유용합니다 (여기에서 수행).

이 기능이 "정상적인 매개 변수"로 취급 될 수 없다는 생각하게 무엇