Einen Maximalwert von einem Binärbaum erhalten

Question

Momentan bin ich Binärbaum und ich möchte den Maximalwert daraus erhalten. Wenn man bedenkt, wie es sowohl String- als auch Int-Werte hat, ist es in alphabetischer Reihenfolge angeordnet. Alles funktioniert einwandfrei, alle Einfügungen, Suchen, Löschen usw. Vorerst müssen wir nur wissen, dass ich hier meinen Baum habe.

typedef struct node 
{ 
    char *name; 
    int count; 
    struct node *l, *r; 
}*link; 

Wie kann ich eine einfache Funktion zu machen, das findet, was die höchste ist count im Baum. Wie ich 20 Knoten im Baum haben kann und nehme an, dass die höchste count 10 ist und es gibt 3 Knoten mit der höchsten count. Es spielt keine Rolle, wie viele es gibt mit 10 die höchste count, ich möchte nur die Funktion 10 zurückgeben. Eine Funktion wie.

int maxValue(link head) 
{ 
    //the help i need with 
} 

Ich habe Online-nachgeschlagen und versucht, einige Beispiele wie die Inorder und all die verschiedenen funtions aber die meisten von ihnen nur alle Werte von links Knoten zu dem am weitesten rechts ein, um platziert, so dass es mir wirklich half nicht finde die maximale Anzahl im Baum, weil meine Organisation nicht von der kleinsten zur größten Nummer organisiert ist.

Answer 1

Rekursion ist in diesem Fall Ihr Freund. Ihre Funktion vergleicht den Wert von sich selbst, das Maximum der linken Seite und das Maximum der rechten Seite und gibt den größten Wert zurück.

int maxValue(link head) 
{ 
    if(head == NULL){ 
     return -1; 
    } 
    int me = head->count; 
    int l = maxValue(head->l); 
    int r = maxValue(head->r); 
    if(me >= l && me >= r) { 
     return me; 
    } else if(l >= me && l >= r){ 
     return l; 
    } else { 
     return r; 
    } 
} 

Bemerkung

Dieser Code ist nicht so allgemein wie man es geschrieben haben könnte. Es wird nur wie erwartet funktionieren, wenn count in der Struktur immer größer gleich Null ist und wenn die Funktion am Anfang eines NULL-Objekts nicht aufgerufen wird, da dann -1 zurückgegeben würde. Bessere Verwendung der @ blazs-Lösung in der Praxis.

Answer 2

ist die Idee, zunächst die Maximalwerte der Teilbäume zu berechnen, und maxLeftmaxRight, ein gegebenes Knotens, und dann max(currVal, maxLeft, maxRight) zurück, wo der Wert currVal im aktuellen Knoten ist.

Hier ist, wie Sie dies in Code direkt auszudrücken:

int maxValue(link head) 
{ 
    assert(head != NULL); 
    int currVal = head->count; 
    if (head->l != NULL) // compute max of the left subtree 
     currVal = max(currVal, maxValue(head->l)); 
    if (head->r != NULL) // compute max of the right subtree 
     currVal = max(currVal, maxValue(head->r)); 
    return currVal; 
} 

Die max könnte ein einfaches Makro, zum Beispiel

#define max(x, y) (x) > (y) ? (x) : (y) 

Answer 3

Um den Maximalwert in einem Baum zu finden, Code nicht nehmen Vorteil der alphabetischen Reihenfolge. Stattdessen muss der gesamte Baum begangen werden. Dies beinhaltet das Überprüfen des aktuellen Knotens und auch des Maximums von jedem der zwei Kinder, links und rechts.

Eine klassische Verbesserung des Gehens eines binären Baums besteht darin, nur auf einem Bein (z. B. linke Seite) und Schleife auf dem anderen (rechts) zu reagieren. Dieses Schleifen-Abrollverfahren kann manchmal durch einen intelligenten Compiler identifiziert werden, der auf beiden Beinen rekursiv ist. Hier unten wird es explizit gemacht.

Dieser Code gibt INT_MIN zurück, sollte das Original head == NULL.

int maxValue(link head) { 
    int max = INT_MIN; 
    while (head) { 
    if (head.count > max) { 
     max = head.count; 
    } 
    int left_max = maxValue(head.left); 
    if (left_max > max) { 
     max = left_max; 
    } 
    head = head.right; 
    } 
    return max; 
} 

Stil: Ich würde eher ein typedef sehen ohne * wie in unten.

typedef struct node { 
    char *name; 
    int count; 
    struct node *l, *r; 
} link;