Java Подсчет одиноких родителей в двоичном дереве поиска?

Question

Я пытаюсь создать метод под названием singleParent(), который подсчитывает количество узлов в BST, у которых есть только 1 ребенок. По какой-то причине, мой singleParent() метод возвращает 0.

Мой код:

BinaryTree

public abstract class BinaryTree { 

    private TreeNode root; 

    public BinaryTree() { 
     this.root = null; 
    } 

    public void setRoot(TreeNode node) { 
     this.root = node; 
    } 

    public TreeNode getRoot() { 
     return this.root; 
    } 

    public boolean isEmpty() { 
     return (this.root == null); 
    } 

    public int singleParent() { 
     return getSingleParents(this.root, 0); 
    } 

    private int getSingleParents(TreeNode t, int count) { 
     if(t != null) { 
      if(t.getLeft() == null && t.getRight() != null) 
       count++; 
      else if(t.getLeft() != null & t.getRight() == null) 
       count++; 
      getSingleParents(t.getLeft(), count); 
      getSingleParents(t.getRight(), count); 
     } 
     return count; 
    } 

    public void swapSubtrees() { 
     doSwap(this.root); 
    } 

    private void doSwap(TreeNode p) { 
     if(p != null) { 
      TreeNode temp = p.getLeft(); 
      p.setLeft(p.getRight()); 
      p.setRight(temp); 
      doSwap(p.getLeft()); 
      doSwap(p.getRight()); 
     } 
    } 

    public void inorder() { 
     doInorderTraversal(this.root); 
    } 

    private void doInorderTraversal(TreeNode t) { 
     if(t != null) { 
      doInorderTraversal(t.getLeft()); 
      System.out.print(t.getValue() + " "); 
      doInorderTraversal(t.getRight()); 
     } 
    } 

    public abstract void insert(Comparable item); 
    public abstract TreeNode find(Comparable key); 

} // end of class 

И мой главный метод:

public static void main(String[] args) { 
    BinaryTree bst = new BinarySearchTree(); 
    bst.insert(14); 
    bst.insert(4); 
    bst.insert(15); 
    bst.insert(3); 
    bst.insert(9); 
    bst.insert(18); 
    bst.insert(7); 
    bst.insert(16); 
    bst.insert(20); 
    bst.insert(5); 
    bst.insert(17); 

    int count = bst.singleParent(); 
    System.out.println(count); 
} 

Это создает дерево, которое выглядит подобный:

  14 
     / \ 
     4  15 
    /\  \ 
     3 9  18 
     / /\ 
     7  16 20 
    /  \  
     5   17 

И поэтому count должен равняться 4, потому что есть 4 узла, которые имеют только 1 ребенка. Любая помощь будет очень высоко ценится.

Answer 1

For some reason, my singleParent() method is returning 0. 

Вы делаете рекурсивные вызовы getSingleParents(t.getLeft(), count); и getSingleParents(t.getRight(), count);, но игнорировать их возвращаемые значения.

По этой причине метод проверяет только, что корневой узел (14) является единственным родителем, а это не так.

На самом деле, вам не нужен параметр count в getSingleParents:

private int getSingleParents(TreeNode t) { 
    int count = 0; 
    if(t != null) { 
     if(t.getLeft() == null && t.getRight() != null) 
      count++; 
     else if(t.getLeft() != null & t.getRight() == null) 
      count++; 
     count += getSingleParents(t.getLeft()); 
     count += getSingleParents(t.getRight()); 
    } 
    return count; 
}