내 BST에서 가장 작은 수를 찾는 방법

지금 내가하려고하는 것은 내 이진 검색 트리 (BST)에서 반복 횟수의 최소값을 찾는 것입니다.내 BST에서 가장 작은 수를 찾는 방법

값을 삽입 할 때 BST가 정상이지만 두 번 동일한 값을 얻으면 그 대신 트리가 종속되지 않는 반복 카운트 값이 증가합니다 (따라서 나는 할 수 없습니다 그냥 최소값을 위해 왼쪽으로 가라.)

최소값을 얻으려고했지만 항상 부족합니다. 작은려고 기능은 다음 findSmallest

public static void main(String[] args) { 

    int x = 0; //random number 

    Random rnum = new Random(); 
    SBT sbt = new SBT(); 

    for(int i = 0; i < 100; i++){ 
     x = rnum.nextInt(20) + 1; 
     sbt.insert(x); 
    } 

    sbt.printLargestCount(); 
    sbt.printSmallestCount(); 
    sbt.FS(); 
    sbt.deleteBoth(); 
    System.out.println("Sum of the key values is: " + sbt.sumKeyValue()); 
    System.out.println("Sum of the repeat counts is: " + sbt.sumReapeatCount()); 

    sbt.inorder(); 
}

입니다 내가 지금 트리의 모든 노드를 통해 이동하는 것을 시도하고 현재 가장 작은 값을 비교하고 값을 얻으려고 노력하는 기능입니다. 노드 repeatCount이 값보다 작 으면 값이 변경되고 글로벌 노드 smallestCount이 변경됩니다.

아래와 같은 전역을 추가했습니다.

private BSTNode root;  
private BSTNode largestCount; 
private BSTNode smallestCount; 
private int sumKeyVal; 
public void FS(){ 
    findSmallest(root, 0); 
    System.out.println("data is: " + smallestCount.data + " repeatCount is: " + smallestCount.repeatCount); 
} 
private void findSmallest(BSTNode r, int val){ 
    if(r == null) return; 
    if(r == root)val = r.repeatCount; 

    if(r.repeatCount < val){ 
     val = r.repeatCount; 
     smallestCount = r; 
     System.out.println(val); 
    } 
    if(r.right == null && r.left == null) 
     return;   
    else if(r.left != null) 
     findSmallest(r.left,val); 
    else if(r.right != null) 
     findSmallest(r.right,val); 
}   

private BSTNode insert(int x, BSTNode t){ 
    if (t == null){ 
     t = new BSTNode(x); 
     smallestCount = t; 
    } 
    else if (x < t.data) 
     t.left = insert(x, t.left); 
    else if (x > t.data) 
     t.right = insert(x, t.right); 
    else 
     t.height = max(height(t.left), height(t.right)) + 1; 
    return t; 
} 
private int height(BSTNode t) { 
    return t == null ? -1 : t.height; 
} 
// Function to max of left/right node 
private int max(int lhs, int rhs) { 
    return lhs > rhs ? lhs : rhs; 
}

여기에 사용되는 노드 클래스는 다음과 같습니다

public class BSTNode { 

    BSTNode left, right; 
    int data; 
    int height; 
    int repeatCount; 

    /* Constructor */ 
    public BSTNode(){ 
     left = null; 
     right = null; 
     data = 0; 
     height = 0; 
     repeatCount = 0; 
    } 
    /* Constructor */ 
    public BSTNode(int n){ 
     left = null; 
     right = null; 
     data = n; 
     height = 0; 
     repeatCount = 0; 
    }  
}

출처

2017-03-29 jhowe

내가 그것을 파악하고 코드가 작동하는 것 같다 테스트. 아래는 변경된 코드 블록입니다.

public void FS(){ 
      findSmallest(root, 0); 
     } 
     private int findSmallest(BSTNode r, int val){ 
      if(r == null) return val; 
      if(r == root)val = r.repeatCount; 

      if(r.repeatCount < val){ 
       val = r.repeatCount; 
       smallestCount = r; 
      } 

      val = findSmallest(r.left,val);  
      val = findSmallest(r.right,val); 

      return val; 

    }

다른 문 및 구걸에 널 (null)에 대한 검사와 함께가는 트리를 통해 이동 된 경우 제거하고 길을 따라 작은 유지하기.

출처

2017-03-30 20:00:06 jhowe

내 BST에서 가장 작은 수를 찾는 방법

답변

관련 문제