Java - 이진 트리에서 노드의 부모 찾기? (일반 트리에서 변환)

Question

일반 트리에서 변환 된 이진 트리가 있습니다. 의미, 주어진 노드의 왼쪽 노드는 해당 노드의 하위 노드이고 주어진 노드의 오른쪽 노드는 해당 노드의 형제 노드입니다.

제 질문은 - 어떻게 노드를 가져다가 부모를 찾을 수있는 방법을 쓸 수 있습니까? (나는 전체 나무를 횡단하여 추측한다)

감사합니다!

Answer 1

올바르게 이해했는지 확인하십시오.

트리 구현에 따라 다릅니다. 일반적으로 트리에는 사이클이 없으며 각 노드에는 자식에 대한 참조가 있습니다. 하지만 다시 한번 이것이 트리의 구현 방법입니다.

리프를 찾고있는 경우 하위가 null 인 기본 사례에 도달 할 때까지 노드의 하위 노드로 계속 순환 할 수 있습니다.

findLeaves (Node n) { 
    if (n == null) 
    return; 
    else if (n.left == null AND n.right == null) 
    return n; // A child 
    else 
    findLeaves(n.left); 
    findLeaves(n.right); 

} 

루트와 동일합니다. 노드가 parent에 대한 참조를 가지고 있고 루트를 찾고 있다면. 부모가 null이 될 때까지 부모에게 반복을 계속합니다. 이는 노드가 부모임을 의미합니다.

findRoot (Node n) { 
    if (n == null) 
    return; 
    else if (n.parent == null) 
    return n; // A root 
    else 
    findRoot(n.parent); 

} 

난 당신이 '가치'정수 변수를 포함하는 노드 클래스가있는 경우이 당신에게

private static BinaryNode getParent(AnyType x, BinaryNode<AnyType> t, BinaryNode<AnyType> parent) { 
     if (t == null) { 
      return null; 
     } else { 
      if (x.compareTo(t.element) < 0) { 
       return getParent(x, t.left, t); 
      } else if (x.compareTo(t.element) > 0) { 
       return getParent(x, t.right, t); 
      } else { 
       return parent; 
      } 
     } 
    } 

Answer 2

도움이되기를 바랍니다. sudo 코드는 다음과 같이 쓸 수 있습니다.

Node find_parent(Node currentNode, Node parentNode, int valueOfChildNode) { 
    Node finalNode = null; 
    if (currentNode->value == valueOfChildNode) return parentNode; 
    if (currentNode->left_child) 
      finalNode = find_parent(currentNode->left_child,valueOfChildNode,currentNode); 
    if (!finalNode && currentNode->right_child) 
      find_parent(currentNode->right_child,valueOfChildNode,currentNode); 
    return finalNode; 
} 

사용자 요구 사항에 따라 변경할 수 있습니다. 아래의 예와 같이 호출 할 수 있습니다.

find_parent(binaryTree->root_node, null, 15);

Answer 3

도움이 될 것입니다 그