2017-12-03 7 views
4

이진 검색 트리에서 발견 된 요소의 깊이를 알려주는이 메서드를 구현하려고합니다.노드를 찾을 수없는 경우 이진 검색 트리에서 어떤 레벨로 이동해야합니까?

제 질문은 요소를 찾지 못했을 때 내 검색에서 종료 (또는 배치) 된 트리의 수준을 어떻게 반환해야합니까?

즉 노드가 트리에 존재하지 않는 경우 노드가 삽입되어야하는 트리의 레벨을 반환해야합니다. 엘리먼트가 트리에서 발견되지 않았을 때 "0"을 반환하고 오히려 그것이 배치되어야하는 레벨을 반환하고 싶지 않습니다. 여기

If I searched for "7", the method should return "3" because that is the level where the search stopped and where in theory the "7" would be added

내가 지금까지 가지고있는 코드이지만, 1

public int depthSearch(Node root, int key){ 
    int depthLevel = 0; 

    if (root==null || root.data==key){ 
     depthLevel++; 
     return depthLevel; 
    } 

    if (root.data > key){ 
     depthSearch(root.left, key); 
     depthLevel++; 
     return depthLevel; 
    }else{ 
     depthSearch(root.right, key); 
     depthLevel++; 
     return depthLevel; 
    } 
} 

내 두 번째 질문은 나의 발견 방법에 깊이 레벨 카운터 로직을 추가하는 것이 만들 것입니다 반환 유지 ? 내 코드를 살펴 복용 사전에

public boolean find(int id){ 
    Node current = root; 
    while(current!=null){ 
     if(current.data==id){ 
      return true; 
     }else if(current.data>id){ 
      current = current.left; 
     }else{ 
      current = current.right; 
     } 
    } 
    return false; 
} 

감사 : 여기

는 방법이다. 그래서 비슷한 질문이있는 스레드를 찾을 수 없었습니다.

+0

당신은'재귀 호출의 결과를 return'하지 않았고, 모든 재귀는 depthSearch를 호출하지만 실제로 반환하고, 정확하게 깊이 0 –

+0

에서 시작 그래서 매번 첫 번째 호출 만 반환합니다. – Meepo

답변

4

제 두 번째 질문은 깊이 찾기 레벨을 카운터 검색 로직에 추가하는 것이 맞습니까?

아니요,이 메서드는 찾을 경우 true을 반환하고 그렇지 않으면 false을 반환합니다. Java에서는 여러 값을 반환 할 수 없습니다 (두 가지를 모두 보유 할 수있는 객체를 만들 수 있지만 그게 ... ...). 그러나 당신이 할 수 있다고하더라도 - 방법은 한 가지를해야합니다!

depthSearch에 대해서는 구현에 문제가 있습니다. 재귀 호출의 결과가 return이 아닙니다.

쉽게하지만 고정 할 수 있습니다

public int depthSearch(Node root, int key) { 

    if (root == null || root.data == key) { 
     return 1; 
    }  
    else if (root.data > key) { 
     return 1 + depthSearch(root.left, key); 
    } else { 
     return 1 + depthSearch(root.right, key); 
    } 
} 
관련 문제