바이너리 트리

Question

미만의 값 검색 대학 업무용 이진 트리에 대한 알고리즘을 만들고 있으며 지정된 값보다 작은 모든 값을 효율적으로 찾는 알고리즘을 개발해야합니다 (순서가 필요합니다).

     10 
        /\ 
        9 11 
       /  \ 
       5   15 
       /\  /\ 
       1 8  13 19 
         /\ 
         12 14 

이것은 내가 생각해 낸 해결책입니다 (위의 그래프는 이진 트리가 어떻게 보이는지 잊어 버린 경우를 대비 한 것입니다).

private BinaryTreeNode root; 
public int[] getBeforeJoinedNum(int num){ 
     usersInOrder = new ArrayList<User>(); 
     beforeNum(num, root); 
     return usersInOrder; 
} 

private void beforeNum(int num, BinaryTreeNode n){ 
     if (n != null){ 
      beforeNum(num, n.getLeft()); 
      int nodeValue = n.getValue(); 
      if (num<nodeValue){ 
       usersInOrder.add(n.getValue()); 
       beforeNum(num, n.getRight()); 
      } 
     } 
    } 

이 알고리즘의 문제점은 불필요한 비교를한다는 것입니다. 예를 들어, 10보다 작은 모든 숫자를 원한다면 코드는 10보다 작 으면 9의 왼쪽 (즉, 1,5,8)을 모두 검사합니다. 반면 9보다 작은 것은 분명히 있어야합니다. 목록에서 비교할 필요없이

어떻게이 알고리즘을보다 효율적으로 만들 수 있습니까? 안타깝게도 데이터 구조가 교과 과정의 핵심이기 때문에 Java 컬렉션 프레임 워크를 사용할 수 없습니다. 나는 또한 beforeNum의 논리 버그를 수정

private void addAll(UserNode n) { 
    if (n == null) return; 
    addAll(n.getLeft()); 
    usersInOrder.add(n.getValue()); 
    addAll(n.getRight()); 
} 

private void beforeNum(int num, UserNode n){ 
    if (n == null) return; 
    if (n.getValue() < num) { 
     addAll(n.getLeft()); 
     usersInOrder.add(n.getValue()); 
     beforeNum(num, n.getRight()); 
    } else { 
     beforeNum(num, n.getLeft()); 
    } 
} 

참고 :

당신은 그들이 재산을 다 알고있는 하위 트리를 들어

Answer 1

, 단지 표준 순서 탐색을 당신은 >와 함께 <을 혼합 올바른 상황에서 올바른 하위 트리를 트래버스하지 않았습니다.

Answer 2

혹시 inorder 검색에 대해 들어 보셨습니까? 아래는 샘플 코드입니다.

public void inOrderTraverse(Node root,UserNode n){ 
     if(root != null&&root.compareTo(n)<0){ 
      inOrderTraverse(root.getLeft()); 
      System.out.print(" "+root.getData()); 
      inOrderTraverse(root.getRight()); 
     } 

    } 

당신은해야합니다 : 그것은 하나 개의 매개 변수 "사용자 노드"를 받아들이고는 "usernode"

public void inOrderTraverse(Node root){ 
     if(root != null){ 
      inOrderTraverse(root.getLeft()); 
      System.out.print(" "+root.getData()); 
      inOrderTraverse(root.getRight()); 
     } 

    } 

여기에 빠른 수정 된 버전이기보다는 여전히 낮은 경우 가로 지르는 정지 있도록 수정 어쨌든 왼쪽에있는 모든 노드를 가로 질렀습니다.