이진 검색 트리에서 부모 찾기

다음은 이진 검색 트리에서 상위 항목을 찾는 코드입니다. 나는 그것이 null이 아닌 부모에게 어떤 가치도 할당하지 않기 때문에 그것이 어떻게 작동 하는지를 이해할 수 없다. 나는 재귀에 처음이다.이진 검색 트리에서 부모 찾기

public Node findParent(Type data) 
{ 
    return findParent(data, root, null); 
} 

public Node findParent(Type x, Node node, Node parent) 
{ 
    if (node == null) { 
     return null; 
    } else if (!(node.data == x)) { 
     parent = findParent(x, node.left, node); 
     if (parent == null) { 
      parent = findParent(x, node.right, node); 
     } 
    } 
    return parent; 
}

출처

2014-11-20 Andy897

내가 인정해야한다 (재귀 설명하기 어렵다) (http://stackoverflow.com/a/27034602/733637) @Eran에 의해, 코드에 보이지 않는 트리를 BST로 사용하면 - 현재 노드의 왼쪽과 오른쪽 서브 트리 모두에 주어진 값을 찾고,'x' 매개 변수에 주어진 값이'x '보다 작거나 큰지 여부를 테스트하지 않습니다 '노드의 멤버. – CiaPan

당신은 재귀 호출에 부모를 null 이외의 값을 할당됩니다

parent = findParent(x, node.left, node); 
            ---- 
parent = findParent(x, node.right, node); 
            ----

parent은 초기 호출에 널 (트리의 루트에 부모가 없기 때문에).

findParent에 대한 각 호출은 값 (x), 노드 (node) 및 해당 노드의 부모 노드 (parent)를 얻습니다. 노드에 해당 값이 있으면 parent가 반환되고, 그렇지 않으면 왼쪽 하위 트리에서 해당 값이 검색되고, 여전히 발견되지 않으면 오른쪽 하위 트리에서 값을 검색합니다.

출처

2014-11-20 08:05:59 Eran

어떻게 그렇게 어리 석을 수 있습니까 – Andy897

나는 (Java에 익숙하지 않은) 그것에 추가 할 또 다른 어리석은 질문을 가지고 있습니다 ... 왜 여기에 두 가지 방법이 있습니다 .. 하나의 공개 및 다른 개인. 왜 개인 메서드를 공개하고 현재의 공용 메서드를 제거 할 수없는 이유는 무엇입니까? – Andy897

@ Andy897 두 가지 방법 모두 공개이지만 두 번째 방법은 비공개로 간주됩니다. 이것을 private으로 만드는 것은 외부 세계로부터'findParent (Type data)'의 구현을 숨 깁니다. 만약 당신이 제안했다면, 이제 private 메서드의 호출자는'findParent (data)'에 대한 간단한 호출 대신'findParent (data, root, null)'을 호출해야 할 것이다. – Eran

여기에 몇 가지 의견을 달았습니다. 명확하지 않은지 말해봐. 에서 [답]뿐만 아니라,

// The method 
public Node findParent(Type x, Node node, Node parent) 
{ 
    // if this node is null, return null, cause this 
    // is not the path you are looking for 
    if (node == null) { 
     return null; 
     // if this is not the node we are looking for, 
    } else if (!(node.data == x)) { 
     // We look in the left node. 
     parent = findParent(x, node.left, node); 
     // If its not found parent will be null 
     if (parent == null) { 
      // So we go look to the right 
      parent = findParent(x, node.right, node); 
     } 
    } 
    // Eventually we can return the parent. 
    // If this was the node we were looking for, 
    // We can return parent without changing it. 
    // If it was not, this algorithm searched in its subtrees 
    // If its not there than parent is null. 
    return parent; 
}

출처

2014-11-20 08:10:45

이진 검색 트리에서 부모 찾기

답변

관련 문제