計數的節點以二進制搜索樹

Question

我需要創建作爲一個參數的二進制搜索樹的根節點的遞歸方法。這個遞歸方法將返回整個二叉搜索樹中節點總數的int值。

這是我到目前爲止有：

public class BinarySearchTree<E> extends AbstractSet<E> 
{ 
protected Entry<E> root; 


//called by the main method 
public int nodes() 
{ 
    return nodes(root); 
}  

//nodes() will count and return the nodes in the binary search tree 

private int nodes(Entry<E> current) 
{  
    if(current.element != null) 
    { 
     if(current.left == null && current.right == null) 
     { 
      if(current.element == root.element) 
      return 1;     

      deleteEntry(current);    
      return 1 + nodes(current.parent); 
     } 
     else if(current.left != null && current.right == null)   
      return nodes(current.left); 

     else if(current.left == null && current.right != null) 
      return nodes(current.right); 

     else if(current.left != null && current.right != null) 
      return nodes(current.left) + nodes(current.right);  
    } else return 1; 
    return 0; 
} 

主要方法調用，像這樣的節點：

 System.out.println ("\nThis section finds the number of nodes " 
      + "in the tree"); 

     System.out.println ("The BST has " + bst.nodes() + " nodes"); 

所以我被順序行駛，一旦我得到運行搜索到沒有孩子的節點，我會刪除當前節點並返回到父節點並繼續。我運行了上述方法的調試，並且當程序最終計數並刪除根節點左側和右側上的所有節點並嘗試返回1時，程序崩潰時發生NullPointerException（）。

這是對於我的實驗室來說，這個方法必須是遞歸的。

我很失落在這一點上，沒有人知道我在做什麼錯？

Answer 1

你在刪除後current：deleteEntry(current);，您使用current.parent在return 1 + nodes(current.parent);

可能是這樣的投擲NullPointerException異常的原因..

Answer 2

你有幾個問題：

• 你刪除你計算它們的節點？ nodes()應該清除樹？
• 你治療root==null，root!=null&left==null&&right==null，root!=null&left!=null&right==null等作爲單獨的個案。他們不是。你有三種情況下，這並非完全排斥：
  • 如果當前節點不爲空，添加一個計數。 （這應該總是這樣的情況。在那裏它可能是假的唯一情況是，如果當前節點== root，我們可以檢測並避開那事前）
  • 如果當前節點有左子，加上左孩子的數量。
  • 如果當前節點有一個正確的子節點，請添加正確的子節點數。
• 你正在回溯向上樹爲一些不合理的理由。看起來它與刪除節點有關...？

但我認爲最重要的是，你沒有給予足夠的自主權給Entry s。 ：P

節點可以指望自己的孩子。相信它。

class Entry<E> { 
    ... 

    int count() { 
     int result = 1; 
     if (left != null) result += left.count(); 
     if (right != null) result += right.count(); 
     return result; 
    } 
} 

public int nodes() { 
    return (root == null) ? 0 : root.count(); 
} 

如果你的老師是不稱職的，並一些節點計數功能堅稱節點外，你可以做你試圖做同樣的事情：

private int nodes(Entry<E> current) { 
    int result = 1; 
    if (current.left) result += nodes(current.left); 
    if (current.right) result += nodes(current.right); 
    return result; 
} 

public int nodes() { 
    return (root == null) ? 0 : nodes(root); 
} 

但是，教師應在我看來，被解僱。 Entry類是真實樹; BinarySearchTree實際上只是一個引用根的容器。

另外請注意，我不給一個該死的parent s。如果我們從根開始計數，並且每個節點統計它的孩子，統計他們的孩子等等，那麼所有的節點都會被計算出來。

Answer 3

你正在使這種方式太複雜。面向對象編程的基本思想是你信任對象來完成他們知道答案的工作。所以如果我是父母，我可以數我自己，我讓我的孩子自數，等等。

private int nodes(Entry<E> current) { 
    // if it's null, it doesn't exist, return 0 
    if (current == null) return 0; 
    // count myself + my left child + my right child 
    return 1 + nodes(current.left) + nodes(current.right); 
} 

Answer 4

嘿，我有一個非常乾淨的計數爲二叉樹的實現：

public class Binary<T> where T: IComparable<T> 
{ 
    private Node _root; 

    public int Count => _root.Count; 

    public void Insert(T item) 
    { 
     Node newNode = new Node(item); 
     if (_root == null) 
      _root = newNode; 
     else 
     { 
      Node prevNode = _root; 
      Node treeNode = _root; 
      while (treeNode != null) 
      { 
       prevNode = treeNode; 
       treeNode = newNode.Item.CompareTo(treeNode.Item) < 1 ? treeNode.Left : treeNode.Right; 
      } 
      newNode.Parent = prevNode; 
      if (newNode.Item.CompareTo(prevNode.Item) < 1) 
       prevNode.Left = newNode; 
      else 
       prevNode.Right = newNode; 
     } 
    } 

    public class Node 
    { 
     public T Item; 

     public Node Parent; 
     public Node Left; 
     public Node Right; 

     public Node(T item, Node parent = null, Node left = null, Node right = null) 
     { 
      Item = item; 
      Parent = parent; 
      Left = left; 
      Right = right; 
     } 

     public int Count 
     { 
      get 
      { 
       int count = 1; 
       count += Left?.Count ?? 0; 
       count += Right?.Count ?? 0; 
       return count; 
      } 
     } 
    } 
} 

也許這可以幫助你瞭解如何實現一類用於計數的簡單的二進制樹。

該實現通過樹中相應節點的計數來訪問計數。

讓我現在如果你不熟悉的.NET 4.6

Answer 5

public int countNodes(Node root){ 
    // empty trees always have zero nodes 
    if(root == null){ 
     return 0; 
    } 

    // a node with no leafes has exactly one node 
    // note from editor: this pice of code is a micro optimization 
    // and not necessary for the function to work correctly! 
    if(root.left == null && root.right == null){ 
     return 1; 
    } 

    // all other nodes count the nodes from their left and right subtree 
    // as well as themselves 
    return countNodes(root.left) + countNodes(root.right) + 1; 
}