Aufgabe: Overwriteall mit BinaryTree (Rekursiv)

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: Overwriteall mit BinaryTree (Rekursiv)

Beitrag von Hallo »

Hi,

Ich habe diesen Code für die Aufgabe overwriteall rekursiv für BinaryTree aufgeschrieben.
Hat jemand vielleicht was zu verbessern ?

Code: Alles auswählen

public boolean overwriteall(TreeNode<T> root, T elem1, T elem2){

	if(root==null){
	return false;}
	
	return overwriteallHelp(root, elem1, elem2, false);
	}
	
	
	
public boolean overwriteall(TreeNode<T> root, T elem1, T elem2, boolean found){	

	if(root == null){return found;}

	else 
	if(root.key.equals(elem2)){
	root.key= elem1;
	found = true;}
	return overwriteall(root.left,elem1,elem2,true) || 
			overwriteall(root.right, elem1, eleme2, true);	
			}
			

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

Re: Aufgabe: Overwriteall mit BinaryTree (Rekursiv)

Beitrag von joshimoo »

der Code wird so nicht funktionieren, da es sich bei dem || operator um einen logischen Operator handelt.
Dieser hat eine Short Circuit Funktion, bedeutet das wenn die linke Seite bereits true ist wird die rechte Seite nicht mehr evaluiert.
Was du also schon mal bräuchtest ist der boolsche Operator |

Code: Alles auswählen

 return overwriteall(root.left,elem1,elem2,true) || overwriteall(root.right, elem1, eleme2, true);   
Des weiteren ist der found Parameter unnötig.

bei den ganzen Aufgaben geht es immer nur um Tree Traversal, daher würde ich mir die (DFS) Pre Order, In Order, Post Order Traversal Strategien mal anschauen, außerdem Level Order (BFS) und diese alle mal iterativ und rekursiv implementieren.

Hab dir mal ein Beispiel geschrieben, wie man die Aufgabe mit preorder lösen kann.
Kannst diese ja mal in Post Order ändern und berichten ;)

https://ideone.com/KqkbxV für den kompletten Code inklusive printTree und co

Code: Alles auswählen

	public static <T> boolean overwriteall(TreeNode<T> root, T find, T replace) {
		// base case
		if(root == null) { return false; }
 
		// pre order traversal
		boolean found = false;
		if(root.key.equals(find)) { 
			found = true; 
			root.key = replace;
		}
 
		// you cannot use || since that will short circuit
		// and therefore the right part of the tree will not be processed
		// if their is an element on the left part already
		return found | overwriteall(root.left, find, replace) | overwriteall(root.right, find, replace);
	}

Antworten

Zurück zu „AuD: Programmieraufgaben“