BST의 n 번째 항목 가져 오기

Question

BST의 n 번째 항목이 보유한 데이터를 반환하려고합니다. 카운터를 사용하여 inorder 순회를 수행하려고합니다. 카운터가 n보다 큰 경우 현재를 반환합니다. 마디. 현재 코드가 항상 첫 번째 항목을 반환하는 것으로 보이고 논리가 잘못된 부분을 볼 수 없습니다. 나는 n 번째 및 inOrder 메서드 만 썼고 나머지는 제공되었습니다. 나는 내가 너무 자주 카운터를 증가시키고 있다고 생각한다. 아래에서 테스트 할 주요 메소드를 게시 할 것이다.

import java.util.NoSuchElementException; 

public class BST { 
    private BTNode<Integer> root; 

    public BST() { 
     root = null; 
    } 


    public boolean insert(Integer i) { 
     BTNode<Integer> parent = root, child = root; 
     boolean goneLeft = false; 

     while (child != null && i.compareTo(child.data) != 0) { 
      parent = child; 
      if (i.compareTo(child.data) < 0) { 
       child = child.left; 
       goneLeft = true; 
      } else { 
       child = child.right; 
       goneLeft = false; 
      } 
     } 

     if (child != null) 
      return false; // number already present 
     else { 
      BTNode<Integer> leaf = new BTNode<Integer>(i); 
      if (parent == null) // tree was empty 
       root = leaf; 
      else if (goneLeft) 
       parent.left = leaf; 
      else 
       parent.right = leaf; 
      return true; 
     } 
    } 

    public int greater(int n) { 
     if (root == null) { 
      return 0; 
     } 
     else { 
      return n; 
     } 
    } 

    int c = 0; 
    public int nth(int n) throws NoSuchElementException { 
     BTNode<Integer> node = null; 
     if (root == null) { 
      throw new NoSuchElementException("Element " + n + " not found in tree"); 
     } 
     else { 
      if (root != null){ 
       node = inOrder(root, n); 
      } 
     } 
     return node.data; 
    } 

    public BTNode inOrder(BTNode<Integer> node, int n) { 
     c++; 
     while (c <= n) { 
      if (node.left != null) { 
       inOrder(node.left, n); 
      } 
      c++; 
      if (node.right != null) { 
       inOrder(node.right, n); 
      } 
     } 
     return node; 
    } 
} 

class BTNode<T> { 
    T data; 
    BTNode<T> left, right; 

    BTNode(T o) { 
     data = o; 
     left = right = null; 
    } 
} 


public class bstTest { 
    public static void main(String[] args) { 
     BST tree = new BST(); 
     tree.insert(2); 
     tree.insert(5); 
     tree.insert(7); 
     tree.insert(4); 
     System.out.println(tree.nth(2)); 
    } 
} 

Answer 1

고려해야 할 불변의 점은 n = sizeOfLeftSubtree + 1 일 때 해당 노드를 반환한다는 것입니다. n이 적 으면 왼쪽으로 가십시오. n이 더 큰 경우 오른쪽으로 이동하여 sizeOfLeftSubtree + 1에 의해 n을 줄입니다. 첫 번째 요소 (가장 왼쪽 요소)에 n = 1을 매핑합니다.

하위 트리의 크기를 재귀 적으로 계산하거나 모든 루트 (모든 노드가 하위 트리의 루트)에 크기를 저장할 수 있습니다. 삽입 방법 (스택/큐에 저장된 모든 노드를 방문하고 if 새 노드가 추가되어 모든 크기가 1 씩 증가합니다.

크기가 저장되면 복잡성은 O (log n)가됩니다. 그렇지 않으면 O (n^2)가 될 수 있습니다.

public int nth(int n) throws NoSuchElementException { 
if(sizeOfTree(this.root) < n || n < 1) 
    throw new NoSuchElementException("Element " + n + " not found in tree"); 

BTNode<Integer> root = this.root; 
boolean found = false; 
do{ 
    int sizeOfLeftSubtree = sizeOfTree(root.left); 
    if(sizeOfLeftSubtree + 1 == n){ 
    found = true; 
    }else if(n < sizeOfLeftSubtree+1){ 
    root = root.left; 
    }else if(sizeOfLeftSubtree+1 < n){ 
    root = root.right; 
    n -= sizeOfLeftSubtree+1; 
    } 
}while(!found); 

return root.data; 
} 

public int sizeOfTree(BTNode<Integer> root){ 
if(root == null) 
    return 0; 
else 
    return sizeOfTree(root.left) + 1 + sizeOfTree(root.right); 
} 

Answer 2

inOrder 메서드에서 node을 변경하지 마십시오.

public BTNode inOrder(BTNode<Integer> node, int n) { 
    c++; 
    while (c <= n) { 
     if (node.left != null) { 
      // **** Add this - or something. 
      node = inOrder(node.left, n); 
     } 
     c++; 
     if (node.right != null) { 
      // **** Add this - or something. 
      node = inOrder(node.right, n); 
     } 
    } 
    return node; 
} 

수정 하시려는 버그는 아니지만 분명히 코드에 문제가있는 것 같습니다.