Finden Maximum von einem Baum

Question

Ich versuche, die maximale Anzahl von einem bestimmten Baum zu finden:

(define-struct (Some T) 
    ([value : T])) 

(define-type (Option T) 
    (U 'None (Some T))) 

(define-type BST (U 'E Nd)) 

(define-struct Nd 
    ([root : Integer] 
    [lsub : BST] 
    [rsub : BST])) 

(: maxi : BST Integer -> Integer) 
(define (maxi x acc) 
    (match x 
     ('E acc) 
((Nd ro ls rs) 
    (cond 
     ((> ro acc) (maxi ls ro)) 
     (else 
     (maxi rs acc)))))) 

Das obige Zitat richtig funktioniert nicht, wenn ich folgendes eingeben:

(maxi (Nd 1 (Nd 2 (Nd 4 (Nd 8 'E' E) (Nd 9 'E' E)) (Nd 5 'E' E)) (Nd 3 (Nd 6 'E' E)) (Nd 7 'E' E))) 0)

Kann mir bitte jemand helfen?

Vielen Dank!

Answer 1

So, hier ist Ihr Test:

(maxi 
    (Nd 
     1 
     (Nd 2 
     (Nd 4 
      (Nd 8 'E 'E) 
      (Nd 9 'E 'E)) 
     (Nd 5 'E 'E)) 
     (Nd 3 
     (Nd 6 'E 'E) 
     (Nd 7 'E 'E))) 
    0) 

Und hier ist, was passiert:

acc root what to do? 
    --------------------------------- 
    0 1  go left with acc = root 
    1 2  idem 
    2 4  idem 
    4 8  idem 
    8 E  return 8 

Wenn Sie Ihre Eingabe Bäume erwarten, dass die binary search tree Eigenschaft gerecht zu werden, die besagt, dass Werte auf der linken Unterbaum sind immer größer als root und die Werte des rechten Teilbaums sind alle kleiner oder gleich, dann ist Ihr Testbaum ein fehlerhafter BST, da 9 größer als 4 ist.

Durch der Weg, wenn Sie eine BST hätten, wo würde der Maximalwert liegen?

Wenn der Baum jedoch nur ein zufälliger Baum ist, müssen Sie das Maximum beider Unterbäume und den Wurzelwert berechnen, bevor Sie den maximalen Gesamtwert bestimmen können.

Im Grunde wollen Sie tun:

(tree-max (Nd root left right)) = (max root 
             (tree-max left) 
             (tree-max right)) 

Wenn Sie es rekursiv tun wollen, werden Sie ein Problem in dem Basisfall auftreten, weil Sie einen maximalen Wert für einen leeren Blattknoten zur Verfügung zu stellen haben: Jeder Wert, den Sie auswählen, macht Ihren Code für einen Baum falsch, der Werte genau unter diesem Wert enthält. Nehmen wir an, Sie wählen Null und berechnen das Maximum eines Baumes mit nur streng negativen Zahlen, dann ist Null die falsche Antwort, weil sie nicht im Baum erscheint (was könnten Sie tun?).

Sie können wählen, einen Akkumulator anstelle von Rekursion zu verwenden, aber in diesem Fall benötigen Sie zwei Akkumulatoren: das Maximum bis jetzt und die Liste der Subtrees, die als nächstes besucht werden müssen. Im Grunde ersetzen Sie den Aufruf-Stack durch einen Heap-allokierten Stack.

Ich kann derzeit nicht testen Sie den folgenden Code, aber hier ist eine mögliche Implementierung:

(define tree-max (tree greatest todo) 
    (match tree 
    ('E greatest (if (null? todo) 
       greatest 
       (tree-max (first rest) 
          greatest 
          (rest todo)) 
    ((Nd root left right) (tree-max left 
            (max greatest root) 
            (cons right todo))))