Binärbaum (Methoden) - Versionsgeschichte

Akaibel: /* Implementierung */

2026-01-23T20:46:25Z

Implementierung

← Nächstältere Version		Version vom 23. Januar 2026, 20:46 Uhr
Zeile 165:		Zeile 165:

	===Implementierung===		===Implementierung===
			''am Beispiel eines Baumes, der Personen enthält''
	<code>		<code>
	public List<~~Object~~> levelorder(BinaryTree<~~Object~~> pTree){		public List<Person> levelorder(BinaryTree<Person> pTree){
	'''//Linearisierung'''		'''//Linearisierung'''
	List<BinaryTree<~~Object~~>> baumListe = new List<>();		List<BinaryTree<Person>> baumListe = new List<>();
	baumListe.append(pTree);		baumListe.append(pTree);
	baumListe.toFirst();		baumListe.toFirst();
	while(baumListe.hasAccess()){		while(baumListe.hasAccess()){
	BinaryTree<~~Object~~> aktuell = baumListe.getContent();		BinaryTree<Person> aktuell = baumListe.getContent();
	if(!aktuell.getLeftTree().isEmpty()){		if(!aktuell.getLeftTree().isEmpty()){
	baumListe.append(aktuell.getLeftTree());		baumListe.append(aktuell.getLeftTree());
Zeile 186:		Zeile 186:
	// von jedem Element (Typ: BinaryTree!)		// von jedem Element (Typ: BinaryTree!)
	// die Wurzel auslesen und an ergebnisListe anhaengen		// die Wurzel auslesen und an ergebnisListe anhaengen
	List<~~Object~~> ergebnisListe = new List<>();		List<Person> ergebnisListe = new List<>();
	baumListe.toFirst();		baumListe.toFirst();
	while(baumListe.hasAccess()){		while(baumListe.hasAccess()){
	BinaryTree<~~Object~~> aktuellerBaum = baumListe.getContent();		BinaryTree<Person> aktuellerBaum = baumListe.getContent();
	~~Object~~ aktuelleWurzel = aktuellerBaum.getContent();		Person aktuelleWurzel = aktuellerBaum.getContent();
	ergebnisListe.append(aktuelleWurzel);		ergebnisListe.append(aktuelleWurzel);
	baumListe.next();		baumListe.next();

Akaibel: /* Vorgehensweise */

2026-01-23T20:42:03Z

Vorgehensweise

← Nächstältere Version		Version vom 23. Januar 2026, 20:42 Uhr
Zeile 150:		Zeile 150:
	Die Idee der Linarisierung ist die folgende:		Die Idee der Linarisierung ist die folgende:

	'''Linearisierung:'''		'''Linearisierung: Baumliste erstellen'''
	# eine Hilfsliste <code>baumListe</code> wird angelegt; in diese Hilfsliste kommen nur Bäume!		# eine Hilfsliste <code>baumListe</code> wird angelegt; in diese Hilfsliste kommen nur Bäume!
	# der ganze Baum wird in <code>baumListe</code> gepackt, d.h. <code>baumListe</code> hat jetzt ein Element.		# der ganze Baum wird in <code>baumListe</code> gepackt, d.h. <code>baumListe</code> hat jetzt ein Element.
Zeile 158:		Zeile 158:
	# Jetzt hat man in <code>baumListe</code> eine Liste aller Teilbäume von <code>pTree</code>.		# Jetzt hat man in <code>baumListe</code> eine Liste aller Teilbäume von <code>pTree</code>.
	## Diese Liste kann jetzt für die Sachlogik verwendet werden.		## Diese Liste kann jetzt für die Sachlogik verwendet werden.
	'''Sachlogik:'''		'''Sachlogik: Ergebnisliste erstellen'''
	# eine Ergebnisliste <code>ergebnisListe</code> wird angelegt; in <code>ergebnisListe</code> kommen die Knoten in der Levelorder-Reihenfolge.		# eine Ergebnisliste <code>ergebnisListe</code> wird angelegt; in <code>ergebnisListe</code> kommen die Knoten in der Levelorder-Reihenfolge.
	# <code>baumListe</code> wird mit einer Schleife durchlaufen. Bei jedem Schleifendurchlauf wird...		# <code>baumListe</code> wird mit einer Schleife durchlaufen. Bei jedem Schleifendurchlauf wird...

Akaibel: /* Implementierung */

2026-01-18T18:18:24Z

Implementierung

← Nächstältere Version		Version vom 18. Januar 2026, 18:18 Uhr
Zeile 114:		Zeile 114:

	<code>		<code>
	public void einfuegen(~~BinaryTree<Integer> pTree,~~ int pZahl) {		//Beispiel-Attribut
			private BinaryTree<Integer> suchbaum;

			public void einfuegen(int pZahl) {
	//Hilfsbaum definieren, damit man pTree nicht "zersägt":		//Hilfsbaum definieren, damit man pTree nicht "zersägt":
	'''BinaryTree<Integer> b = ~~pTree~~;'''		'''BinaryTree<Integer> b = suchbaum;'''
	'''while(!b.isEmpty()){'''		'''while(!b.isEmpty()){'''
	int wurzel = b.getContent();		int wurzel = b.getContent();
	'''// UPDATE von pTree'''		'''// UPDATE von pTree'''
	if(pZahl < wurzel){		if(pZahl < wurzel){
			// "links abbiegen"
	'''b = b.getLeftTree();'''		'''b = b.getLeftTree();'''
	}		}
	else{		else{
			// "rechts abbiegen"
	'''b = b.getRightTree();'''		'''b = b.getRightTree();'''
	}		}

Akaibel: /* Implementierung */

2026-01-18T18:14:51Z

Implementierung

← Nächstältere Version		Version vom 18. Januar 2026, 18:14 Uhr
Zeile 75:		Zeile 75:
	'''//rekursive Methode'''		'''//rekursive Methode'''
	'''//Parameter vom Typ BinaryTree''' ist notwendig für rekursive Aufrufe!		'''//Parameter vom Typ BinaryTree''' ist notwendig für rekursive Aufrufe!
	~~public~~ int summe(BinaryTree<Integer> pTree){		private int summe(BinaryTree<Integer> pTree){
	int ergebnis = 0;		int ergebnis = 0;

Akaibel: /* Rekursion */

2026-01-18T18:14:26Z

Rekursion

← Nächstältere Version		Version vom 18. Januar 2026, 18:14 Uhr
Zeile 48:		Zeile 48:
	<div style="margin:0; margin-right:10px; border:1px dotted #000008; padding: 0em 1em 1em 1em; background-color:#F9F9F9;text-align:left">		<div style="margin:0; margin-right:10px; border:1px dotted #000008; padding: 0em 1em 1em 1em; background-color:#F9F9F9;text-align:left">

	'''<u>Bestandteile einer rekursiven Methode:</u>'''		'''<u>Bestandteile einer rekursiven Methode für Binärbäume:</u>'''
			* Die rekursive Methode braucht als einen '''Parameter einen Binärbaum''', damit man rekursiv für den linken bzw. rechten Teilbaum aufrufen kann.
			** Die rekursive Methode wird häufig aus einer '''Rahmenmethode''' aufgerufen.
	* eine '''Abbruchbedingung''' oder mehrere Abbruchbedingungen.<br> Diese hängen vom Sachzusammenhang ab - in der Regel braucht man mindestens eine Abbruchbedingung für einen leeren Binärbaum.		* eine '''Abbruchbedingung''' oder mehrere Abbruchbedingungen.<br> Diese hängen vom Sachzusammenhang ab - in der Regel braucht man mindestens eine Abbruchbedingung für einen leeren Binärbaum.
	* '''Wurzel auslesen''' ''(=Wurzelbehandlung)''		* '''Wurzel auslesen''' ''(=Wurzelbehandlung)''
Zeile 61:		Zeile 63:

	<code>		<code>
			//ein Beispiel-Attribut
			private BinaryTree<Integer> suchbaum;

			'''//Rahmenmethode'''
			public int summe(){
			// die Rahmenmethode '''delegiert''' die Aufgabe an die rekursive Methode.
			// dabei übergibt sie den zu behandelnden Baum.
			return summe(suchbaum);
			}

			'''//rekursive Methode'''
			'''//Parameter vom Typ BinaryTree''' ist notwendig für rekursive Aufrufe!
	public int summe(BinaryTree<Integer> pTree){		public int summe(BinaryTree<Integer> pTree){
	int ergebnis = 0;		int ergebnis = 0;

Akaibel: /* Blätter */

2023-02-15T20:35:07Z

Blätter

← Nächstältere Version		Version vom 15. Februar 2023, 20:35 Uhr
Zeile 232:		Zeile 232:
	<code>		<code>
	public List blaetter(BinaryTree<Object> pTree) {		public List blaetter(BinaryTree<Object> pTree) {
	List ergebnis = new List();		List<Object> ergebnis = new List<>();

	if (pTree.isEmpty()) {		if (pTree.isEmpty()) {
Zeile 240:		Zeile 240:
	if (pTree.getLeftTree().isEmpty() && pTree.getRightTree().isEmpty()){		if (pTree.getLeftTree().isEmpty() && pTree.getRightTree().isEmpty()){
	// pTree ist ein Blatt!		// pTree ist ein Blatt!
	ergebnis.append(pTree);		ergebnis.append(pTree.getContent());
	return ergebnis;		return ergebnis;
	}		}

Akaibel: /* Implementierung */

2023-01-21T11:57:00Z

Implementierung

← Nächstältere Version		Version vom 21. Januar 2023, 11:57 Uhr
Zeile 97:		Zeile 97:
	Als Beispiel wird die Methode '''einfuegen''' für einen mit Zahlen gefüllten Suchbaum implementiert.		Als Beispiel wird die Methode '''einfuegen''' für einen mit Zahlen gefüllten Suchbaum implementiert.

	[https://youtu.be/UGrrFuV3zjY Pfaddurchlauf durch einen Binärbaum implementieren (Youtube)]		[https://youtu.be/UGrrFuV3zjY Erklärvideo: Pfaddurchlauf durch einen Binärbaum implementieren (Youtube)]

	<code>		<code>

Akaibel am 21. Januar 2023 um 11:56 Uhr

2023-01-21T11:56:17Z

← Nächstältere Version		Version vom 21. Januar 2023, 11:56 Uhr
Zeile 3:		Zeile 3:
	[[Kategorie:Informatik-Abitur]]		[[Kategorie:Informatik-Abitur]]
	[[Kategorie:Datenstrukturen(IF)]]		[[Kategorie:Datenstrukturen(IF)]]
	~~<font color='red'>'''Diese Seite entspricht dem Abi 17 (und folgenden)'''</font>~~

	Hier werden die '''Standard-Strategien''' für das Durchlaufen von [[allgemeiner Binärbaum ab Abi 2017\|Binärbäumen]] vorgestellt:		Hier werden die '''Standard-Strategien''' für das Durchlaufen von [[allgemeiner Binärbaum ab Abi 2017\|Binärbäumen]] vorgestellt:
Zeile 16:		Zeile 15:
	* [https://youtu.be/to2supzEiO4 rekursive Methoden für Binärbäume implementieren (Youtube)]		* [https://youtu.be/to2supzEiO4 rekursive Methoden für Binärbäume implementieren (Youtube)]
	* [https://youtu.be/SjniaclqvFs Prinzip und Implementierung der Levelorder-Traversierung (Youtube)]		* [https://youtu.be/SjniaclqvFs Prinzip und Implementierung der Levelorder-Traversierung (Youtube)]
			* [https://youtu.be/UGrrFuV3zjY Pfaddurchlauf durch einen Binärbaum implementieren (Youtube)]

	=Fachbegriffe=		=Fachbegriffe=
Zeile 96:		Zeile 96:
	===Implementierung===		===Implementierung===
	Als Beispiel wird die Methode '''einfuegen''' für einen mit Zahlen gefüllten Suchbaum implementiert.		Als Beispiel wird die Methode '''einfuegen''' für einen mit Zahlen gefüllten Suchbaum implementiert.

			[https://youtu.be/UGrrFuV3zjY Pfaddurchlauf durch einen Binärbaum implementieren (Youtube)]

	<code>		<code>

Akaibel: /* Linearisierung */

2023-01-18T15:47:24Z

Linearisierung

← Nächstältere Version		Version vom 18. Januar 2023, 15:47 Uhr
Zeile 121:		Zeile 121:
	[https://youtu.be/SjniaclqvFs Erklärvideo: Prinzip und Implementierung der Levelorder-Traversierung]		[https://youtu.be/SjniaclqvFs Erklärvideo: Prinzip und Implementierung der Levelorder-Traversierung]

	'''Linearisierung''' ist eine Strategie, wie man rekursive Strukturen (z.B. einen Binärbaum) komplett durchlaufen kann, '''''OHNE eine rekursive Methode zu verwenden'''''.		'''Linearisierung''' ist eine Strategie, wie man rekursive Strukturen (z.B. einen Binärbaum) komplett durchlaufen kann, <br/>'''''OHNE eine rekursive Methode zu verwenden'''''.

	===Vorgehensweise===		===Vorgehensweise===

Akaibel: /* Erklärvideos */

2023-01-18T15:46:33Z

Erklärvideos

← Nächstältere Version		Version vom 18. Januar 2023, 15:46 Uhr
Zeile 14:		Zeile 14:

	=Erklärvideos=		=Erklärvideos=
	[https://youtu.be/to2supzEiO4 rekursive Methoden für Binärbäume implementieren (Youtube)]		* [https://youtu.be/to2supzEiO4 rekursive Methoden für Binärbäume implementieren (Youtube)]
			* [https://youtu.be/SjniaclqvFs Prinzip und Implementierung der Levelorder-Traversierung (Youtube)]

	=Fachbegriffe=		=Fachbegriffe=