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

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.

Answer 2

1. Die Tiefe:

---

En Tiefe eines Knotens im Baum ist die Länge des Pfades von der Wurzel zum Knoten. Die Tiefe des Baums ist die maximale Tiefe aller Knoten des Baums.

2. Höhe:

---

En Höhe des Knotens ist die Länge des Pfades von diesem Knoten zum tiefsten Knoten im Baum. Die Höhe des Baumes ist die Länge des Pfades vom Wurzelknoten bis zum tiefsten Knoten im Baum (z. B.: die Höhe des Baumes im obigen Beispiel ist vier (die Kanten zählen, nicht die Knoten)). Ein Baum mit nur einem Knoten hat die Höhe Null.

Weitere Informationen über die Grundlagen von Bäumen finden Sie unter: EINFÜHRUNG UND EIGENSCHAFTEN VON BÄUMEN

Answer 3

Ich wollte diesen Beitrag schreiben, weil ich CS studiere und wir mehr und 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 gelehrt 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 in Programmen verursacht! Vielen Dank!

Von der OpenDSA Datenstrukturen & Algos Buch :

Wenn n ₁ , n ₂ ,...,n _k ist eine Folge von nein dass n _i ist die Mutter von n _i +1 für 1<=i<k, dann ist diese Folge ein Pfad von n ₁ zu n _k . Die Länge des Weges ist k1. Wenn es einen Pfad vom Knoten R zum Knoten M gibt, dann ist R ein Vorfahre von M, und M ist ein Nachkomme von R. Somit sind alle Knoten im Baum Nachkommen der Wurzel des Baumes, während die Wurzel der Vorfahre aller aller Knoten ist. Die Tiefe eines Knotens M im Baum ist die Länge der Pfades von der Wurzel des Baumes zu M. Die Höhe eines Baumes ist eins mehr als die Tiefe des tiefsten Knotens des Baumes. A befinden sich auf der Ebene d des Baums. Die Wurzel ist der einzige Knoten auf der Ebene 0, und seine Tiefe ist 0.

Abbildung 7.2.1: Ein binärer Baum. Knoten A ist die Wurzel. Die Knoten B und C sind die Kinder von A. Die Knoten B und D bilden zusammen einen Teilbaum. Knoten B hat zwei Kinder: Sein linkes Kind ist der leere Baum und sein rechtes Kind ist D. Die Knoten A, C und E sind Vorfahren von G. Die Knoten D, E und F bilden die Ebene 2 des Baums; der Knoten A befindet sich auf Ebene 0. Die Kanten von A zu C zu E zu G bilden einen Pfad der Länge 3. Die Knoten D, G, H und I sind Blätter. Die Knoten A, B, C, E und F sind interne Knoten. Die Tiefe von I ist 3. Die Höhe dieses Baums ist 4.

Answer 4

Die Antwort von Daniel A.A. Pelsmaeker und Yesh Analogy ist ausgezeichnet. Ich möchte ein bisschen mehr von hackerrank Tutorial hinzufügen. Hoffentlich hilft es auch ein bisschen.

• Die Tiefe (oder Ebene) eines Knotens ist seine Entfernung (d.h. die Anzahl der Kanten) vom Wurzelknoten des Baums.
• Die Höhe ist die Anzahl der Kanten zwischen dem Wurzelknoten und dem am weitesten entfernten Blatt.
• height(node) = 1 + max(height(node.leftSubtree),height(node.rightSubtree)) .
  Beachten Sie die folgenden Punkte, bevor Sie das folgende Beispiel lesen.
• Jeder Knoten hat eine Höhe von 1.
• Die Höhe des leeren Teilbaums ist -1.
• Die Höhe eines einzelnen Elementbaums oder Blattknotens ist 0.
  

Answer 5

Tiefe Wie viele Kanten befinden sich oberhalb des Knotens, der die Tiefe eines Knotens ist?
Höhe Höhe eines Knotens: Wie viele Kanten befinden sich unterhalb des Knotens, der die Höhe eines Knotens ist?

 Node1 // depth = 0 and height = 2 => root node
  |
 / \
Node2 Node3 //depth = 1 and height = 1
|     |
Node4 Node5  //depth = 2 and height = 0  => leaf node```