이진 검색 트리에서 리프가 아닌 노드를 계산하는 방법은 무엇입니까?

Question

내 코드와 함께 새로운 질문을 게시하고 있습니다. 이진 검색 트리의 리프가 아닌 노드를 계산하려고합니다. 리프가 아닌 메서드를 만들고 테스트 클래스에서 호출하려고합니다. 누군가 나를 도울 수 있습니까? 다음은 코드입니다.

public class BST { 
    private Node<Integer> root; 

    public BST() { 
     root = null; 
    } 

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

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

     if (child != null) 
      return false; 
     else { 
      Node<Integer> leaf = new Node<Integer>(i); 
      if (parent == null) 
       root = leaf; 
      else if (gLeft) 
       parent.left = leaf; 
      else 
       parent.right = leaf; 
      return true; 
     } 
    } 

    public boolean find(Integer i) { 
     Node<Integer> n = root; 
     boolean found = false; 

     while (n != null && !found) { 
      int comp = i.compareTo(n.data); 
      if (comp == 0) 
       found = true; 
      else if (comp < 0) 
       n = n.left; 
      else 
       n = n.right; 
     } 

     return found; 
    } 

    public int nonleaf() { 
     int count = 0; 
     Node<Integer> parent = root; 

     if (parent == null) 
      return 0; 
     if (parent.left == null && parent.right == null) 
      return 1; 
    } 

} 

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

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

Answer 1

리프가 아닌 노드의 개수에만 관심이 있다면 트리를 한 번 통과하고 한 번만 유지하면됩니다. 왼쪽 또는 오른쪽 노드 증가 카운트를 가지도록 노드를 만날 때마다.