Aufgabe: SecMax binärer Suchbaum

Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Aufgabe Nr. x = 1..4 lassen Sie Ihr Betreff bitte mit "x: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Hallo
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 22. Apr 2015 19:03

Aufgabe: SecMax binärer Suchbaum

Beitrag von Hallo »

Hier nochmal ein Code den ich implementiert habe.
So akzeptabel, oder hat jemand ein Vorschlag für Verbesserung ?

Code: Alles auswählen

public T secMax(TreeNode<T> root, Comparator<T> cmp){
		
			if(root==null){
			return null;}
		
		Stack<TreeNode<T>> stack = new Stack<TreeNode<T>>();
		
		stack.push(root);
		
		T secMax = null;
		T max = root.key;
		while(!stack.isEmpty()){
		
		T aktelem = stack.pop();
			
			if(aktelem.right!=null){
			secMax = aktelem.key;
			max = aktelem.right.key;
			stack.push(aktelem.right);
			}
			if(aktelem.right == null && aktelem.left!=null){
					secMax = aktelem.left.key;
					stack.push(aktelem.left);	}
			
			
			}
			return secMax;
	}

joshimoo
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 25. Apr 2015 17:16

Re: Aufgabe: SecMax binärer Suchbaum

Beitrag von joshimoo »

Ich hab mir den Code nicht durchgelesen.

Sie brauchen bei einem Binären Suchbaum keinen Stack.
Um ein Maximum Element zu finden.

Malen sie sich mal ein paar Suchbäume auf und überlegen sie mal wo da das Maximum und 2te Maximum überall liegen kann.
Annahme Baum enthält keine Duplikate, dann können sie das Problem mit 2 Pointern lösen.

Hallo
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 162
Registriert: 22. Apr 2015 19:03

Re: Aufgabe: SecMax binärer Suchbaum

Beitrag von Hallo »

Auch bei einem iterativen Lösungsweg ?

joshimoo
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 25. Apr 2015 17:16

Re: Aufgabe: SecMax binärer Suchbaum

Beitrag von joshimoo »

Sie pushen und popen in jeder Iteration 1 Element.
Dies können sie durch einfache Zuweisung ersetzen.

Das 2te Maximum ist predecessor des Maximums und diese kann sich an lediglich 2 Stellen im Suchbaum befinden ;)
Malen sie sich mal 2/3 Suchbaueme mit dem Pfad zum Maximum und danach dem Pfad zum 2ten Maximum auf.

Dann werden sie feststellen
- das sich das 2te Maximum im Pfad des Maximum befindet
- oder es einen Charakteristischen Punkt gibt, an dem die zwei sich trennen ;)

ich denke das sollte ihr Verständnis fördern.

Antworten

Zurück zu „AuD: Programmieraufgaben“