Подсчет узлов в двоичном дереве поиска

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"); 

Так я бегу поиск, путешествуя в порядке, как только я получаю к узлу без детей я бы удалял текущий узел и возвращался к родительскому узлу и продолжал. Я выполнил отладку метода, который у меня выше, и программа вылетает с помощью NullPointerException(), когда он, наконец, подсчитывает и удаляет все узлы с левой и правой стороны корневого узла и пытается вернуть 1.

Это для моей лаборатории метод ДОЛЖЕН быть рекурсивным.

Я очень потерялся в этот момент, кто-нибудь знает, что я делаю неправильно?

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. : 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 - это real дерево; BinarySearchTree действительно просто контейнер для ссылки на корень.

Также обратите внимание, что я не наплеваю на parent. Если мы начнем считать из корня, и каждый узел подсчитывает его дочерние элементы, которые подсчитывают их дочерние элементы и т. Д. И т. Д. ... тогда все узлы будут учитываться.

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; 
}