최소 및 최대가 주어진 이진 트리 재귀 탐색

Question

질문 (재귀 여야 함) : 이진 트리의 루트와 최소값과 최대 값을 사용하는 함수를 작성하고 트리 사이에있는 모든 노드를 찾습니다. 다른 노드에 대한 가능한 최소한의 방문을 가진 그 값

public boolean inRange(Node node, int max, int min) 
{ 
    return root.element() < max && root.elemnt() > min; 
} 
public void inRangeFinder(Node root, int max, int min) 
{ 
    if (root == null) return; //break 
    if(inRange(root, max, min)) 
     visit(root); //mark as found 
    finder(root.leftChild()); 
    finder(root.rightChild()); 
} 

내 질문은 if 문이 필요합니까? 그리고 그것은 왼쪽과 오른쪽 서브 트리 트래버스에서 문제를 일으킬 것인가? 그리고 가장 중요한 것은 이것이 가능한 최소한의 방문 만있는 방법일까요?

Answer 1

업데이트 : 죄송합니다. 프로그램이 java로 작성되었음을 알 수 없습니다. 나는 자바 사용자가 아니기 때문에 아마도 그 대답은 옳지 않을 것이다. 실례합니다.

예, 첫 번째 if 문이 필요합니다. 문을 닫으면 프로그램에서 NULL 포인터 을 방문하여 런타임 오류가 발생합니다.

기본적으로 왼쪽 첫 번째 dfs 검색이므로 모든 노드에서 한 번만 을 방문합니다. 트리가 구성되지 않은 경우이 방법은 일 수 있습니다. 그러나 나무가 조직 된 나무, 인 경우에 당신은 에 특정한 나무 유형을 적응시키기 위하여 당신의 방법을 재정의해야한다 최소 방문.

재귀 적으로 사용하려면 함수 이름 을 일관되게 정의해야합니다.

public void finder(Node root, int max, int min) 
      //^^^^^ be the same with your recursive call 
{ 
    if (root == null) return; //break 
    if(inRange(root, max, min)) 
     visit(root); //mark as found 
    finder(root.leftChild(),max,min); 
          //^^same arguments 
    finder(root.rightChild(),max,min); 
          //^^ 
} 

Answer 2

당신은 if 문을 필요가 없습니다보다 간단한 방법으로 구성되어 나무가있는 경우.

정말 트리 구현에 따라 다릅니다. 내 opionion에서 중위 트리

-find value with min key. 
-travers in order 
    - and check if result of 
     in order traversal result meets max condition 

에 대한

의사 코드는 당신도 특정 범위를 검사 할 필요가 없습니다. 순서

예

    5 
       4  8  
      2  6 9  
       3    

단지

그래서 범위 사이의 선택은 특정 seuence을 찾기 위해 좌측 리프 계산 시간을 사용하여 각 노드를 통과 수단. 최소값에 대해 Inorder를 실행하는 것보다 을 구현하십시오. 그리고 당신의 구현 인 이 max에 대한 inorder 값을 찾는 동안 그것을 실행하십시오.

하지만이 과정의 결과를 저장하여 원하는 순서를 얻으십시오.

희망 조금 조금 도울 수 있습니다