wenn der Durchmesser eines Baumes Berechnung warum Höhe allein Berechnung nicht ausreicht

Question

den Durchmesser des Baums Bei der Suche nach sehen wir in das Maximum der folgenden:

1: Durchmesser des linken Unterbaum

2: Durchmesser der rechte Unterbaum

3: Höhe des linken Unterbaum + Höhe des rechten Unterbaum + 1.

, warum diese drei ist notwendig? warum 3. allein ist nicht ausreichend. Nehmen wir ein einfaches Beispiel von 3-Knoten-Baum und 2-Knoten-Baum. In der ehemaligen 3. Punkt ergibt sich 1 + 1 + 1 = 3. während in letzterem Fall 3. Punkt ergibt 0 + 1 + 1 = 2.

In diesem Fall müssen wir das Maximum von drei finden. Plz erklären

Answer 1

Betrachten Sie den folgenden Baum:

  [A] 
     /
     [B] 
    / \ 
    [C]  [D] 
/  \ 
[E]   [F] 

Die Höhe des linken Teilbaum von A 3 ist; die Höhe des rechten Teilbaum von A ist 0. Daher Zustand 3 gibt uns 3 + 0 + 1 = 4.

Aber der Durchmesser des Baumes ist 5: Die Knoten auf dem Weg zwischen E und F sind E, C , B, , F.

Wie the page you linked to erklärt, gilt Bedingung 3 nur für Pfade, die durch die Wurzel des Baums gehen. Wenn der längste Pfad zwischen zwei Blättern nicht durch die Wurzel geht, fällt sie unter der Bedingung, 1 oder 2. Die erste Abbildung auf dieser Seite auch ein Beispiel zeigt:

der richtige Baum mit einem Durchmesser von 9 hat , aber Bedingung 3 ergibt nur 5 + 2 + 1 = 8.