# Binärbaum
###### tags: `Algorithmen`
Rico Meiner [CC0 1.0](https://creativecommons.org/publicdomain/zero/1.0/deed.de)
* [Artikel](https://hackmd.io/R7oqQcVUS6S7Fg3fmy4uqQ?view)
* [Präsentation](https://hackmd.io/@JadeOER-IT/rJDwajTX9#/)
* <kbd>ESC</kbd> Überblick
* <kbd>Leertaste</kbd> nächste Folie
* <kbd>g</kbd> Zur Folie springen
* <kbd>.</kbd> Ausblenden
* <kbd>s</kbd> Referentenansicht
[toc]
---
## Binärbaum erstellen
Erstelle aus der Folge 12, 4, 17, 15, 8, 24, 2 einen Binärbaum!
----
Folge **12**, 4, 17, 15, 8, 24, 2
```graphviz
digraph BinBaumErstellen {
12 [color=green style=filled] # neuer Eintrag markiert
}
```
<br>
1. Schritt
12 ist der Wurzelknoten.
----
Folge 12, **4**, 17, 15, 8, 24, 2
```graphviz
digraph BinBaumErstellen {
4 [color="green" style="filled"]
12 -> 4
}
```
2. Schritt
4 ist kleiner als 12, also wird es links platziert und ist der linke Kindknoten von 12.
----
Folge 12, 4, **17**, 15, 8, 24, 2
```graphviz
digraph BinBaumErstellen {
graph [ordering="out"] # korrekt "sortierte" Reihenfolge
17 [color=green style=filled]
12 -> 4
12 -> 17
}
```
3. Schritt
17 ist größer als 12, also wird es rechts platziert und ist der rechte Kindknoten von 12.
----
Folge 12, 4, 17, **15**, 8, 24, 2
```graphviz
digraph BinBaumErstellen {
graph [ordering="out"]
15 [color=green style=filled]
12 -> 4
12 -> 17
17 -> 15
}
```
4. Schritt
15 ist größer als 12 und kleiner als 17 und wird daher links von 17 platziert und ist der linke Kindknoten von 17.
----
Folge 12, 4, 17, 15, **8**, 24, 2
```graphviz
digraph BinBaumErstellen {
graph [ordering="out"]
8 [color=green style=filled]
12 -> 4
12 -> 17
17 -> 15
4 -> 8
}
```
5. Schritt
**8** ist kleiner als 12 und größer als 4, also wird es rechts von 4 platziert und ist der rechte Kindknoten von 4.
----
Folge 12, 4, 17, 15, 8, **24**, 2
```graphviz
digraph BinBaumErstellen {
graph [ordering="out"]
24 [color=green style=filled]
12 -> 4
12 -> 17
17 -> 15
4 -> 8
17 -> 24
}
```
6. Schritt
**24** ist größer als 12 und größer als 17, also wird es rechts von 17 platziert und ist der rechte Kindknoten von 17.
----
Folge 12, 4, 17, 15, 8, 24, **2**
```graphviz
digraph BinBaumErstellen {
graph [ordering="out"]
2 [color=green style=filled]
12 -> 4
12 -> 17
17 -> 15
17 -> 24
4 -> 2
4 -> 8
}
```
7. Schritt
**2** ist kleiner als 12 und kleiner als 4, also wird es links von 4 platziert und ist der linke Kindknoten von 4.
---
## Binärbaum Knoten entfernen
Löschen Sie die 17 aus ihrem Baum.
Ausgangslage:
```graphviz
digraph BinBaumErstellen {
graph [ordering="out"]
12 -> 4
12 -> 17
17 -> 15
17 -> 24
4 -> 2
4 -> 8
}
```
----
```graphviz
digraph BinBaumErstellen {
graph [ordering="out"]
17 [color=red style=filled]
12 -> 4
12 -> 17
17 -> 15
17 -> 24
4 -> 2
4 -> 8
}
```
<br>
1. Schritt
**17** entfernen
----
```graphviz
digraph BinBaumErstellen {
graph [ordering="out"]
24 [color=green style=filled]
12 -> 4
12 -> 24
24 -> 15
4 -> 2
4 -> 8
}
```
Der Grund dafür ist, dass der Kindknoten auf der rechten Seite leer sein kann und der Kindknoten auf der linken Seite nicht leer sein kann. Nach dem Streichen von 17 bleibt also 15 unangetastet und 24 nimmt den Platz von 17 ein.
---
TODO
- [ ] Suchen im Binärbaum
- [ ] Algorithemn für einfügen, löschen und suchen
- [ ] Erläuterungen und Einsatzgebiete hinzufügen
{"title":"Binärbaum","breaks":true,"slideOptions":"{\"transition\":\"fade\",\"theme\":\"white\",\"title\":\"Binärbaum einfügen/entfernen\"}","description":"Rico Meiner CC0 1.0","contributors":"[{\"id\":null,\"add\":7,\"del\":0}]"}