Renvoie la différence entre la clé la plus basse et la plus haute - Arbre de recherche binaire

Question

Il s'agit d'un document d'examen sur les arbres de recherche binaire que je suis en train d'essayer. Je n'ai aucun moyen de vérifier si la sortie est correcte car je ne suis pas capable de construire 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 la méthode span, l'en-tête était donné pour nous.

Answer 1

Vous devez définir deux méthodes, min(Tree) et max(Tree), puis 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écursive si vous le souhaitez.

Notez que min et max n'ont pas ont pour être leurs propres méthodes. Si vous ne vous inquiétez pas pour les faire tenir leurs propres unités, vous pouvez mettre tout en span comme ceci:

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