أعد الفرق بين أدنى وأعلى شجرة بحث ثنائية

Question

هذه ورقة امتحان سابقة عن أشجار البحث الثنائية التي أحاولها. ليس لدي أي طريقة للتحقق مما إذا كان الإخراج صحيحًا لأنني غير قادر على بناء أحد هذه الأشياء.

السؤال في العنوان

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

هل يمكن لأي شخص أن يقترح ما أحتاج إلى تغييره للحصول على 5/5 علامات: D - الشيء الوحيد الذي يتعين علينا فعله هو كتابة span الطريقة ، أعطيت الرأس لنا.

Answer 1

تحتاج إلى تحديد طريقتين ، min(Tree) و max(Tree), ، ومن بعد span(Tree t) يعرف ب max(t) - min(t). span لا ينبغي أن تكون متكررة ، ولكن يمكنك القيام بها min و max عودية إذا كنت تريد.

لاحظ أن min و max لا لديك لتكون أساليبهم الخاصة. إذا كنت لا تهتم بجعلها تقف كوحدات خاصة بها ، فيمكنك وضع كل شيء فيه span مثله:

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