Was ist der Unterschied zwischen Baumtiefe und Baumhöhe?

Question

Dies ist eine einfache Frage aus der Algorithmentheorie.
Der Unterschied zwischen ihnen besteht darin, dass in einem Fall die Anzahl der Knoten und im anderen Fall die Anzahl der Kanten auf dem kürzesten Weg zwischen Wurzel und konkretem Knoten gezählt wird.
Was ist was?

Answer 1

Ich habe gelernt, dass Tiefe und Höhe die Eigenschaften eines Knoten :

• En Tiefe eines Knotens ist die Anzahl der Kanten zwischen dem Knoten und dem Wurzelknoten des Baums.
  Ein Wurzelknoten hat eine Tiefe von 0.

• En Höhe eines Knotens ist die Anzahl der Kanten auf der längster Weg vom Knoten zu einem Blatt.
  Ein Blattknoten hat eine Höhe von 0.

Eigenschaften eines Baum :

• En Höhe eines Baumes wäre die Höhe seines Wurzelknotens,
  oder gleichwertig die Tiefe des tiefsten Knotens.

• En Durchmesser (oder Breite ) eines Baumes ist die Anzahl der Knotenpunkte auf dem längsten Weg zwischen zwei beliebigen Blattknoten. Der unten stehende Baum hat einen Durchmesser von 6 Knoten.

Answer 2

Höhe und Tiefe eines Baumes sind gleich...

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

Die Höhe wird berechnet, indem vom gegebenen Knoten bis zum tiefstmöglichen Blatt getraversiert wird.

Die Tiefe wird aus dem Traversal von Root zum angegebenen node..... berechnet.

Answer 3

Nach Cormen et al. Introduction to Algorithms (Appendix B.5.3) ist die Tiefe eines Knotens X in einem Baum T definiert als die Länge des einfachen Pfades (Anzahl der Kanten) vom Wurzelknoten von T zu X. Die Höhe eines Knotens Y ist die Anzahl der Kanten auf der längste abwärts gerichteter einfacher Pfad von Y zu einem Blatt. Die Höhe eines Baumes ist definiert als die Höhe seines Wurzelknotens.

Beachten Sie, dass ein einfacher Pfad ein Pfad ohne Wiederholungspunkte ist.

Die Höhe eines Baum ist gleich der maximalen Tiefe von a Baum . Die Tiefe eines Knotens und die Höhe eines Knotens sind nicht unbedingt gleich. Siehe Abbildung B.6 der 3. Auflage von Cormen et al. für eine Veranschaulichung dieser Konzepte.

Ich habe manchmal Probleme erlebt, bei denen man aufgefordert wurde, Knoten (Scheitelpunkte) statt Kanten zu zählen. Bitten Sie also um Aufklärung, wenn Sie sich nicht sicher sind, ob Sie bei einer Prüfung oder einem Vorstellungsgespräch Knoten oder Kanten zählen sollen.

Answer 4

Ich weiß, es ist seltsam, aber Leetcode definiert Tiefe auch als Anzahl der Knoten im Pfad. In diesem Fall sollte die Tiefe also bei 1 beginnen (immer die Wurzel zählen) und nicht bei 0. Für den Fall, dass jemand die gleiche Verwirrung wie ich hat.

Answer 5

Eine andere Möglichkeit, dieses Konzept zu verstehen, ist die folgende: Tiefe: Zeichnen Sie eine horizontale Linie an der Wurzelposition und betrachten Sie diese Linie als Boden. Die Tiefe der Wurzel ist also 0, und alle ihre Kinder wachsen nach unten, so dass jede Ebene der Knoten die aktuelle Tiefe + 1 hat.

Höhe: Dieselbe horizontale Linie, aber dieses Mal ist die Bodenposition der äußere Knoten, der das Blatt des Baumes ist und aufwärts zählt.