Dies ist eine einfache Frage aus der Algorithmus-Theorie.
Der Unterschied zwischen ihnen besteht darin, dass Sie in einem Fall die Anzahl der Knoten und in einem anderen Fall die Anzahl der Kanten auf dem kürzesten Weg zwischen Wurzel und Betonknoten zählen.
Welcher ist welcher?
algorithm
data-structures
tree
nodes
terminology
Gabriel Ščerbák
quelle
quelle
Antworten:
Ich habe gelernt, dass Tiefe und Höhe Eigenschaften eines Knotens sind :
Die Tiefe eines Knotens ist die Anzahl der Kanten vom Knoten zum Wurzelknoten des Baums.
Ein Wurzelknoten hat eine Tiefe von 0.
Die Höhe eines Knotens ist die Anzahl der Kanten auf dem längsten Pfad vom Knoten zu einem Blatt.
Ein Blattknoten hat eine Höhe von 0.
Eigenschaften eines Baumes :
Die Höhe eines Baumes wäre die Höhe seines Wurzelknotens
oder gleichwertig die Tiefe seines tiefsten Knotens.
Der Durchmesser (oder die Breite ) eines Baums ist die Anzahl der Knoten auf dem längsten Pfad zwischen zwei beliebigen Blattknoten. Der Baum unten hat einen Durchmesser von 6 Knoten.
quelle
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 angegebenen Knoten zum tiefstmöglichen Blatt gewechselt wird.
Die Tiefe wird aus der Durchquerung von der Wurzel zum angegebenen Knoten berechnet.
quelle
Nach Cormen et al. Einführung in Algorithmen (Anhang B.5.3): Die Tiefe eines Knotens X in einem Baum T ist definiert als die Länge des einfachen Pfades (Anzahl der Kanten) vom Wurzelknoten von T nach X. Die Höhe eines Knotens Y beträgt Die Anzahl der Kanten auf dem längsten einfachen Abwärtspfad von Y zu einem Blatt. Die Höhe eines Baums ist definiert als die Höhe seines Wurzelknotens.
Beachten Sie, dass ein einfacher Pfad ein Pfad ohne wiederholte Scheitelpunkte ist.
Die Höhe eines Baumes entspricht der maximalen Tiefe eines Baumes . 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. zur Veranschaulichung dieser Konzepte.
Ich habe manchmal Probleme gesehen, einen zu bitten, Knoten (Eckpunkte) anstelle von Kanten zu zählen. Bitten Sie daher um Klarstellung, wenn Sie nicht sicher sind, ob Sie Knoten oder Kanten während einer Prüfung oder eines Vorstellungsgesprächs zählen sollten.
quelle
Einfache Antwort:
Tiefe:
1. Baum : Die Anzahl der Kanten / Bögen vom Wurzelknoten zum Blattknoten des Baums wird als Tiefe des Baums bezeichnet.
2. Knoten : Die Anzahl der Kanten / Bögen vom Wurzelknoten zu diesem Knoten wird als Tiefe dieses Knotens bezeichnet.
quelle
Ein anderer Weg, um dieses Konzept zu verstehen, ist wie folgt: Tiefe: Zeichnen Sie eine horizontale Linie an der Wurzelposition und behandeln Sie diese Linie als Grund. Die Tiefe der Wurzel ist also 0, und alle untergeordneten Elemente wachsen nach unten, sodass jede Knotenebene die aktuelle Tiefe + 1 hat.
Höhe: Gleiche horizontale Linie, aber diesmal ist die Bodenposition externe Knoten, die das Blatt des Baumes sind und nach oben zählen.
quelle
Ich wollte diesen Beitrag schreiben, weil ich ein CS-Student bin und immer mehr OpenDSA und andere Open-Source-Lehrbücher verwenden. Aus der am besten bewerteten Antwort geht hervor, dass sich die Art und Weise, wie Höhe und Tiefe unterrichtet werden, von einer Generation zur nächsten geändert hat, und ich poste dies, damit jeder weiß, dass diese Diskrepanz jetzt besteht und hoffentlich keine Fehler mehr verursacht Programme! Vielen Dank.
Von dem OpenDSA Data Structures & Algos-Buch :
quelle