Was ist der Unterschied zwischen Baumtiefe und Höhe?

Question

Dies ist eine einfache Frage von Algorithmen Theorie.
Der Unterschied zwischen ihnen ist, dass Sie in einem Fall zählen Anzahl von Knoten und in anderer Anzahl der Kanten auf dem kürzesten Weg zwischen Wurzel und Beton Knoten.
Was was ist?

Answer 1

erfuhr ich, daß Tiefe und Höhe sind Eigenschaften eines node :

• Tiefe eines Knotens ist die Anzahl der Kanten, die von dem Knoten zu dem Wurzelknoten des Baums. Ein Wurzelknoten wird eine größte Tiefe von 0 haben.

• Die Höhe eines Knotens ist die Anzahl der Kanten auf dem längsten Pfad von dem Knoten zu einem Blatt.
  Ein Blattknoten wird ein Höhe von 0.

Eigenschaften von a Baum :

• Höhe ein Baum die Höhe seines Wurzelknoten sein würde, oder in äquivalenter Weise die Tiefe des tiefstenen Knotens.

• Durchmesser (oder Breite ) ein Baum ist die Anzahl von Knoten auf dem längsten Pfad zwischen zwei beliebigen Endknoten . Der Baum unten hat einen Durchmesser von 6 Knoten.

Answer 2

Höhe und Tiefe eines Baumes gleich ...

aber Höhe und Tiefe eines Knotens ist nicht gleich, weil ...

die Höhe wird berechnet, indem von dem gegebenen Knoten zum tiefstmöglichen Blatt durchquert.

Tiefe von Traversierung von der Wurzel zu dem gegebenen Knoten berechnet wird .....

Answer 3

Nach Cormen et al. Introduction to Algorithms (Appendix B.5.3), die Tiefe eines Knotens X in einem Baum T ist als die Länge des einfachen Pfades (Anzahl der Kanten) von dem Wurzelknoten von T zu X definiert, um die Höhe eines Knotens Y die Anzahl der Kanten auf der Seite längste nach unten einfachen Weg von Y zu einem Blatt. Die Höhe des Baumes, wenn die Höhe seines Wurzelknoten definiert ist.

Beachten Sie, dass ein einfacher Weg ist ein Weg ohne Wiederholung Eckpunkten.

Die Höhe eines Baum ist gleich die maximale Tiefe eines Baum . Die Tiefe eines Knotens und die Höhe eines Knotens ist nicht notwendigerweise gleich. Siehe Abbildung B.6 der 3. Auflage von Cormen et al. Eine Darstellung dieser Konzepte.

Ich habe manchmal Probleme gesehen fragen Knoten (Eckpunkte) zu zählen, statt Kanten, fragen Sie so zur Klärung, wenn Sie nicht sicher sind, sollten Sie Knoten oder Kanten während einer Prüfung zählen oder ein Vorstellungsgespräch.

Answer 4

Einfache Antwort:
Tiefe:      
1. Baum : Anzahl der Kanten / arc aus dem Wurzelknoten zu dem Blattknoten des Baumes als die Tiefe des Baumes genannt wird.     
2. Node . Anzahl der Kanten / arc von dem Wurzelknoten zu diesem Knoten als die Tiefe dieses Knotens aufgerufen wird

Answer 5

Ein andere Möglichkeit, dieses Konzept zu verstehen ist wie folgt: Tiefe: Zeichnen Sie eine horizontale Linie an der Wurzel Position und behandelt diese Zeile als Boden. So ist die Tiefe der Wurzel 0, und alle seine Kinder sind nach unten wachsen, so dass jeder Ebene der Knoten die aktuelle Tiefe + 1.

. Höhe: Gleiche horizontale Linie aber dieses Mal die Bodenposition externe Knoten sind, die das Blatt des Baumes ist und nach oben zählen

Answer 6

Ich wollte diesen Beitrag machen, weil ich ein CS-Student Student bin und immer mehr nutzen wir OpenDSA und andere Open-Source-Lehrbücher. Es scheint, wie aus der am besten bewerteten Antwort, dass die Art und Weise der Höhe und Tiefe gelehrt wird von einer Generation zur nächsten geändert hat, und ich bin dieses Posting so jeder ist sich bewusst, dass diese Diskrepanz existiert jetzt und hoffentlich nicht Ursache Fehler in jeder Programme! Danke.

Von der OpenDSA Data Structures & Algos Buch :

  

n ₁ , n ₂ , ..., n _k ist eine Folge von Knoten im Baum solchen   dass n _i ist der Elternteil von n _i +1 für 1 <= i 1 n _k genannt. Die Länge des Weges ist, k-1.   Wenn es einen Weg vom Knoten R an den Knoten M ist, dann ist R ein Vorfahre   M und M ist ein Nachkomme von R. Somit sind alle Knoten im Baum sind   Nachkommen der Wurzel des Baums, während die Wurzel der Vorfahre ist   alle Knoten. Die Tiefe eines Knotens in der Baumstruktur M ist die Länge der   Pfad von der Wurzel des Baumes bis M. Die Höhe eines Baumes ist ein weiteres   als die Tiefe des tiefsten Knoten im Baum. Alle Knoten der Tiefe d   auf Stufe d sind in dem Baum. Die Wurzel ist der einzige Knoten in Ebene 0 ist, und   seine Tiefe ist 0.

     

     

Abbildung 7.2.1: Ein binärer Baum. Der Knoten A ist die Wurzel. Die Knoten B und C   Als Kinder. Die Knoten B und D bilden zusammen einen Unterbaum. Node B   zwei Kinder: Sein linkes Kind ist der leere Baum und sein rechtes Kind   D. Die Knoten A, C und E sind Vorfahren von G. Dem Knoten D, E und F   Make-up-Ebene 2 des Baumes; Knoten A auf dem Pegel 0. Die Kanten von A   auf C bis E bis G einen Pfad der Länge 3. Die Knoten D, G, H und I bilden   Blätter sind. Die Knoten A, B, C, E und F sind interne Knoten. Die Tiefe   von I 3. Die Höhe dieses Baumes ist 4.