如何计算二叉搜索树中的非叶节点？

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

如果你只对非叶节点计数感兴趣，那么你可以遍历树一次并保持一个计数。每当遇到一个节点时，它有左或右节点增量计数。