Was bedeutet es, einen bewurzelten Baum zu bauen? Ich lese die Definition in here, aber selbst wenn wir einen Knoten als Wurzel zuweisen, warum nimmt der Baum nur die folgenden Formen? Ich meine, ich kann einen Wurzelbaum mit 4 Ecken in mehr als den 4 Formen darunter zeichnen? Recht?Was ist ein verwurzelter Baum?
Ich denke, der einzige Unterschied besteht darin, dass ein Knoten in dem Baum ein spezieller Startknoten ist.
Normalerweise sind Bäume rekursiv; Alle Baumknoten sind selbst Bäume. Ein "verwurzelter Baum" ist nur einer, bei dem die Kindknoten anders als ein spezieller Elternknoten markiert sind. Das kann bedeuten, dass ein Algorithmus nicht rekursiv implementiert werden kann oder eine spezielle Bedingung für den Umgang mit dem Wurzelknoten hat.
Das Beispiel, das mir in den Sinn kommt, ist ein rot-schwarzer Baum. Knoten in einem rot-schwarzen Baum sind entweder rot oder schwarz gekennzeichnet. Aber es gibt eine spezielle Regel, dass "der Wurzelknoten immer schwarz ist". Das ist eine spezielle Behandlung, die wir auf die Wurzel und nur auf die Wurzel anwenden müssen. Kinder des Wurzelknotens könnten rot sein; Das bedeutet, dass die untergeordneten Knoten der ersten Ebene des Stammknotens nicht als Stammknoten in ihrem eigenen rot-schwarzen Baum behandelt werden können.
So könnte man erwarten ‚Unterscheidung‘ Code wie
if(node.isRoot):
node.Color = black
Ein freier Baum jeder Knoten in einem binären Suchbaum sein würde; Es spielt keine Rolle, welchen Knoten Sie auswählen, Operationen wie Suchen und Einfügen funktionieren immer gleich. Ihre Algorithmen sind rekursiv. Algorithmen über freie Bäume enthalten niemals eine Frage wie "ist es der Wurzelknoten".
Welche zusätzliche Form können Sie zeichnen? – Thilo
Ich habe gerade daran gedacht, die Ausrichtung von links nach rechts zu ändern. Weißt du, dass es genauso ist, ob ich die Richtung ändere oder die Grafik auf den Kopf hebe? –
Nun, "gleich genug", um keinen wirklichen Unterschied zu machen (hängt natürlich vom Kontext ab). Dies wird Isomorphismus genannt. Sie können die Grafik auf den Kopf stellen, aber es ist immer noch die gleiche Grafik (für einige Definition derselben). – Thilo