Aufgabe: Overwriteall mit BinaryTree (Rekursiv)

[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]

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);
	}