Binärbaum, der Minimum rekursiv findet

Ich habe den minimalen Wert in einem binären Baum gefunden, der kein binärer Suchbaum ist. Allerdings muss ich das rekursiv tun. Was mich verwirrt, ist der Basisfall. Was gebe ich zurück, wenn t null ist? Da ich den zurückgegebenen Wert verwenden werde, um ihn mit dem aktuellen Mindestwert zu vergleichen (denke ich), ist es wichtig, was ich zurückgebe. Danke im Voraus!Binärbaum, der Minimum rekursiv findet

public static Object min(TreeNode t) 
{ 

    if(t == null) 
    return ; 
    else 
    instantiate an object named mini 
    compare it to min(t.getLeft()) 
     if mini is greater than it, mini equals t.getLeft() 
    compare mini to t.getRight()) 
     if mini is greater, mini equals t.getRight 
    return mini 

}

Quelle

2017-02-11 Andrew

Ich weiß nichts über TreeNode in Java, aber wenn ein Objekt null ist, würde ich nur -1 oder möglicherweise 0 zurückgeben. – Ryan

Wie gesagt, + unendlich ist korrekt. Aber ich bin mir nicht sicher, ob das die richtige Frage ist, die du stellst, denn wahrscheinlich ist der richtige Weg, nicht auf Null-Knoten zu rekurrieren. Vielleicht können Sie den Rest Ihres Codes anzeigen? (Es ist auch ein bisschen komisch, als der Rückgabetyp Objekt ist). –

das würde nicht funktionieren, weil 0 könnte größer sein, dass das aktuelle Minimum – Andrew

Sie haben zur Zeit Object als Rückgabetyp von min aber wahrscheinlich etwas präziser werden soll. Wenn der Baum beispielsweise Ganzzahlen enthält, lautet der Rückgabetyp Integer oder Long. Solange es einen vernünftigen Maximalwert für diesen Typ gibt, den min zurückgibt, sollten Sie dies im Basisfall zurückgeben. Wenn Ihre Struktur beispielsweise Ganzzahlen enthält, geben Sie Integer.MAX_VALUE zurück. Warum? Weil Sie garantiert haben, dass alles andere weniger ist als das, so dass der Basisfall die Ergebnisse nicht negativ beeinflusst.

Quelle

2017-02-11 20:51:41

gibt es eine String.MAX_VALUE? – Andrew

@Andrew Was wäre der Maximalwert für einen String? Wie würde das Sinn machen? –

Wenn dies C oder C++ war, könnten Sie einfach Zeiger verwenden. Java hat es nicht. Aber Sie können so etwas simulieren.
Oder Sie können ein Objekt definieren, das Daten und Boolean enthält.

class A { 
    int a; // or whatever you want 
    bool is_null = false; // default value 
} A_NULL = {0, true};

Wenn Sie eine Daten gefunden haben, dann legen Sie die Daten in das Objekt und geben Sie es zurück. Wenn Sie nicht nur A_NULL zurückgegeben haben.

Quelle

2017-02-12 11:37:10 Parker

Binärbaum, der Minimum rekursiv findet

Antwort

Verwandte Themen