Algorithmus 2 Binärbäume vergleichen

[NataLi]

Hallo Leute,
sitze nun schon seit Stunden an dem folgenden Problem:
Ich muss ein Binärbaum mit einem anderen vergleichen.
Hier der Code für die Bäume:

public class SortedBinTree {
		int value;
		SortedBinTree left;
		SortedBinTree right;
		
	SortedBinTree (SortedBinTree left,int value,SortedBinTree right) {
		this.value = value;
		this.left = left;
		this.right = right;}}

Mir fehlt die zündende Idee wie man es anstellen soll...
Hat jemand nen Tip für mich?

 

[Kim Stebel]

prüfen, ob die value felder gleich sind, dann rekursiv prüfen, ob left und right gleich sind. natürlich nicht vergessen, left und right auf null zu prüfen.

 

[NataLi]

Ich komme leider trotzdem nicht weiter. Habe genau mit der Rekursion meine Probleme....

public boolean vergleiche(SortedBinTree baum){
		boolean wahr=false;
		if(this.value==baum.value) wahr=true;
			if (vergleiche(baum.left))wahr=true;
				if (vergleiche(baum.right)){wahr=true;};
				
				return wahr;

 

[Kim Stebel]

statt

if (vergleiche(baum.left))wahr=true;

musst du

if (left.vergleiche(baum.left))wahr=true;

schreiben! ich denke es ist klar warum, oder? das selbe natürlich für right. Ja und dann fehlt nur noch, dass du vorher auf null prüfst. beide null =>true, nur einer =>false.

 

[NataLi]

Es tut mir leid, aber bin wohl schwer vom Begriff...

public boolean vergleiche(SortedBinTree baum){
		boolean wahr=false;
			if(this.value==baum.value) wahr=true;
/*HIER?*/		if((this.left==null)&(baum.left==null))wahr=true;
					if((this.right==null)&(baum.right==null))wahr=true;
						if (left.vergleiche(baum.left))wahr=true; 
							if (right.vergleiche(baum.right))wahr=true; 

			
				
				return wahr;

 

[Kim Stebel]

*händeübermkopfzusammenschlag*
wie schaffst du es in so wenig codezeilen so viele fehler zu machen? warum diese komische indentierung?
also noch mal:
am anfang "wahr" auf true setzen, dann folgendes prüfen, und gegebenenfalls wahr auf false setzen:
baum==null
value!=baum.value
left==null &&baum.left!=null
right==null && baum.right != null
!left.vergleiche(baum.left)
!right.vergleiche(baum.right)

ach übrigens...ich gebe auch nachhilfe in java und anderen Informatikthemen...

 

[NataLi]

Ich weiss nicht, was ich falsch mache....Diese Rekursion ist sehr schwer zu begreifen...Meiner Freundin geht es genauso...

public boolean vergleiche(SortedBinTree baum){
			
		boolean wahr = true;
		if(baum==null) 
		if(value!=baum.value) 
		if((left==null) && (baum.left!=null)) 
		if((right==null) && (baum.right != null)) 
		if(!left.vergleiche(baum.left))
		if(!right.vergleiche(baum.right))
		
			return wahr;
			
		else {wahr=false;}
		return wahr;

class Aufgabe {
	 		
public static void main (String []args)throws CloneNotSupportedException {
		
SortedBinTree d =  new SortedBinTree(null,2, null);
SortedBinTree e =  new SortedBinTree(null,7,null);
SortedBinTree f =  new SortedBinTree(null,15,null);
SortedBinTree g =  new SortedBinTree(null,19,null);
SortedBinTree b =  new SortedBinTree(d,5,e);
SortedBinTree c =  new SortedBinTree(f,18,g);
SortedBinTree a = new SortedBinTree(b,10,c);

SortedBinTree d1 =  new SortedBinTree(null,2, null);
SortedBinTree e1 =  new SortedBinTree(null,7,null);
SortedBinTree f1 =  new SortedBinTree(null,15,null);
SortedBinTree g1 =  new SortedBinTree(null,19,null);
SortedBinTree b1 =  new SortedBinTree(d1,5,e1);
SortedBinTree c1 =  new SortedBinTree(f1,18,g1);
SortedBinTree a1 = new SortedBinTree(b1,10,c1);

System.out.println("Vergleich gelungen? "+ a.vergleiche(a1));

 

[Marco13]

Um Rekursion zu begreifen, muss man zuerst Rekursion begreifen. *brüller*
Naja.

Bei (dieser Art von) Rekursion hat man eigentlich immer...
1. Basisfälle: Fälle, wo das Ergebnis "trivial" ist, und man es einfach zurückgeben kann
2. Die Rekursion: Man teilt das Problem auf, und versucht die (einfacheren) Teilprobleme zu lösen.

Wenn man zwei Bäume mit Wurzelknoten A und B vergleichen will, hat man dann auch hier...:

1. Basisfälle:
Wenn A und B beide 'null' sind, dann sind die Bäume gleich
Wenn entweder A oder B 'null' sind (aber nicht beide), dann sind die Bäume NICHT gleich
Wenn A.value != B.value ist, dann sind die Bäume NICHT gleich

2. Die Rekursion:
Wenn keiner der Basisfälle zutrifft, UND
- die Bäume mit den Wurzelknoten A.left und B.left gleich sind UND
- die Bäume mit den Wurzelknoten A.right und B.right gleich sind
dann sind die Bäume gleich.


Wenn man dass im Pseudocode hinschreibt, hat man schon sowas wie

boolean sindGleich(Node A, Node B)
{
    if (A == null && B == null) return true; // Beide sind 'null' - sie sind gleich
    if (A == null && B != null) return false; // Ein Knoten ist null, der andere nicht -> NICHT gleich
    if (A != null && B == null) return false; // Ein Knoten ist null, der andere nicht -> NICHT gleich
    if (A.value != B.value) return false; // Unterschiedliche Werte -> NICHT gleich

    // Wenn man hier angekommen ist, hat man zwei Knoten mit gleichen Werten. 
    // Jetzt die Rekursion für die linken und rechten Nachfolger:
    return (sindGleich(A.left, B.left) && sindGleich(A.right, B.right));
}

Hm. Das ist schon fast kein "Pseudo" code mehr :roll: Naja.

 

[Beni]

Ich weiss nicht, was ich falsch mache....Diese Rekursion ist sehr schwer zu begreifen...Meiner Freundin geht es genauso...

Dein Problem liegt auch an deiner sparsamen Schreibweise. Mach ein paar Klammern und korrekte Einrückung, dann sieht die Welt schon besser aus.

Wenn man das macht, kommt folgendes raus. Kann das stimmen?

public boolean vergleiche(SortedBinTree baum){
			
		boolean wahr = true;
		if(baum==null){
		  if(value!=baum.value){
		    if((left==null) && (baum.left!=null)){
		      if((right==null) && (baum.right != null)){
		        if(!left.vergleiche(baum.left)){
		          if(!right.vergleiche(baum.right)){
		            return wahr;
		          }
		          else {
		            wahr=false;
		          }
		        }
		      }
		    }
		  }
		}
		return wahr;
}

Nein! Dann machen wir es doch Schritt für Schritt...

public boolean vergleiche(SortedBinTree baum){
		if(baum==null){
		  // ne, wohl nicht richtig
		  return false;
		}

		if(value!=baum.value){
		  // wahrscheinlich auch falsch
		  return false;
		}

		if(!left.vergleiche(baum.left)){
		  // wenn die linken nicht gleich sind, ist es wohl falsch
		  return false;
		}

		// etc etc...
}

 

[Leroy42]

public boolean isSame(SortedBinTree baum) {
  return baum != null &&
            value == baum.value &&
            (left  ==null ? baum.left  ==null : left.isSame(baum.left)) &&
            (right==null ? baum.right==null : right.isSame(baum.right));
}