Renvoie la différence entre la clé la plus basse et la plus élevée - l'arbre de recherche binaire

Question

Il s'agit d'un document d'examen passé sur les arbres de recherche binaires que j'essaie. Je n'ai aucun moyen de vérifier si la sortie est correcte car je ne suis pas capable de construire l'une de ces choses.

La question est dans le titre

class Tree{
    Tree left;
    Tree right;
    int key;

   public static int span(Tree tree)
   {
        if ( tree == null ){
             return null;
        }

        if( tree.left != null)
             int min = span(tree.left);
         }

        if( tree.right != null){
             int max = span(tree.right);
         }
         return max - min;
    }
}

Quelqu'un pourrait-il suggérer ce que je dois changer pour obtenir 5/5 points: D - La seule chose que nous devons faire est d'écrire le span Méthode, l'en-tête a été donné pour nous.

Answer 1

Vous devez définir deux méthodes, min(Tree) et max(Tree), alors span(Tree t) est défini comme max(t) - min(t). span lui-même ne devrait pas être récursif, mais vous pouvez faire min et max récursif si vous le souhaitez.

Notez que min et max n'a pas ont être leurs propres méthodes. Si vous ne vous souciez pas de les faire être leurs propres unités, vous pouvez tout mettre dans span comme ça:

int span(Tree t) {
   Tree tMin = t;
   while (tMin.left != null) {
      tMin = tMin.left;
   }

   Tree tMax = t;
   while (tMax.right != null) {
      tMax = tMax.right;
   }

   return tMax.key - tMin.key;
}