如何計算二叉搜索樹中的非葉節點？

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

如果你只對非葉節點計數感興趣，那麼你可以遍歷樹一次並保持一個計數。每當遇到一個節點時，它有左或右節點增量計數。