Unterschied sortierter und geordneter Binärbaum?
Ist das die gleiche Bedingung für einen Binärbaum? Sortiert heißt doch das die Knoten jeweils links kleiner und rechts größer vom Wurzelknoten sein müssen.
1 Antwort
Ein Binärbaum heißt geordnet, wenn jeder innere Knoten ein linkes und eventuell zusätzlich ein rechtes Kind besitzt (und nicht etwa nur ein rechtes Kind), sowie der linke Knoten „kleiner“, der rechte Knoten „größer“ als der Betrachtungsknoten ist.
In einem sortierten Binärbaum (englisch: sorted binary tree) enthält der linke Teilbaum eines Knotens nur Werte die kleiner (oder gleich) als der Wert des Elternknotens sind, und der rechte Teilbaum nur Werte die größer (oder gleich) als der Wert des Elternknotens sind.
D.h. ein geordneter ist zugleich ein sortierter aber nicht unbedingt umgekehrt
Vielen Dank für deine Antwort. Meinst du mit dem Elternknoten des Teilbaums die Wurzel? Also bei beiden Arten sind die Knoten links kleiner und rechts größer als ihre Elternknoten. Aber ein Sortierter Binärbaum enthält jeweils in seinem linken Teilbaum kleinere Knoten als die Wurzel und der rechte größere als die Wurzel oder?