If null Abfrage

[xyfreeman]

Servus!

Ich will eine Methode schreiben, die abfragt, ob ein Knoten (in einem Binärsuchbaum) zwei Kinder hat.

Also dachte ich mir

if(actNode.getLeft() == null && actNode.getRight() == null){
...
}

müsste reichen. Allerdings passiert da einfach nichts bzw. wird wohl "false" zurückgegeben auch wenn die actNode wirklich keine Kinder hat!

Kann mir da jmd. sagen warum?

Ahja, Node sieht so aus:

 public Node(Node<T> parent, T item){
    this.parent = parent;
    this.rightchild = null;
    this.leftchild = null;
    this.item = item;
  }

public Node<T> getLeft(){
    return leftchild;
  }

 

[Morgyr]

Edit: hat sich erübrigt

 

[xyfreeman]

Habe jetzt schon alles mögliche durchprobiert, aber Java scheint recht unbeeindruckt.

Also ich hab's jetzt anders gelöst, indem ich nur einen Parameter der Node (Item) prüfe. Aber die Frage ansich bleibt im Raum und interessiert mich immer noch : )

Kann Java nichts damit anfangen, weil hier mehrere Parameter null sind und nicht nur einer?

 

[xyfreeman]

*seufz*

Habe das Problem auch bei

if(actNode.getLeft().getItem() == null && actNode.getRight().getItem() != null)

Das != null scheint Java nicht so aufzugreifen wie ich. Die Items sind vom generischen Typ T, aber für die gilt null doch auch oder nicht?

 

[LordLuzifer]

Hab mal das folgende probiert:

public static void main(String[] args) {
        Object o1 = new Object();
        Object o2 = new Object();
        System.out.println(o1 != null && o2 != null);
        o1 = null;
        o2 = null;
        System.out.println(o1 != null && o2 != null);
        System.out.println(o1 == null && o2 == null);
    }

und bekomme als Ergebnis

true
false
true

So sollte es sein, und genau das müsste mit deinem Node auch funktionieren. Bist du dir sicher, dass der Fehler nicht woanders liegt?

 

[xyfreeman]

Eigentlich schon. Ich poste mal was ich bisher habe. Möchte die delete Methode eines Binären Suchbaums schreiben.

 public void delete(T x){ 
  
  Node<T> preNode = root;
  Node<T> actNode = root;
  actNode = find(x);
  preNode = preFind(x);
  boolean flag = true;
    
//    while(flag){
      if(isInTree(x)){	
        if(actNode.getLeft().getItem() == null & actNode.getRight().getItem() == null){ 	      // 1.Fall
          if(x.compareTo(preFindGetItem(x)) < 0){
            preNode.setLeft(null);
//            flag = false;
//            break;
          }
          else if (x.compareTo(preFindGetItem(x)) > 0){
            preNode.setRight(null);
//            flag = false;
//            break;
          }
        }
      }
      if(isInTree(x)){  
        if(actNode.getLeft().getItem() == null && actNode.getRight().getItem() != null){		// 2.Fall
          if(x.compareTo(preFindGetItem(x)) < 0){												
            preNode.setLeft(actNode.getRight());												 
//            flag = false;
//            break;
          }
          else if (x.compareTo(preFindGetItem(x)) > 0){											
            preNode.setLeft(actNode.getLeft());
//            flag = false;
//            break;
          }
        }
      }
      if(isInTree(x)){
        if(actNode.getLeft().getItem() != null && actNode.getRight().getItem() == null){ 		
          if(x.compareTo(preFindGetItem(x)) < 0){												
            preNode.setRight(actNode.getRight());
//            flag = false;
//            break;
          }
          else if (x.compareTo(preFindGetItem(x)) > 0){											
            preNode.setRight(actNode.getLeft());
//            flag = false;
//            break;
          }
        }
      }
    }
//  }

Ignoriert die while Schleife. Damit wollte ich nur etwas testen.

Der Dritte Fall fehlt noch ganz (man muss ja die Suchbaumeigenschaften beachten, woraus sich 3 zu unterscheidene Fälle ergeben), weil die delete Methode für den zweiten Fall nicht funktioniert. Wobei plötzlich auch der erste Fall anders bearbeitet wird. Seit ich die delete Methode für den zweiten Fall erweitert habe...

*edit*

Mhm, du hast auch immer nur zwei Operatoren der selben Art. Vielleicht liegt es daran? Vielleicht kommt Java mit einmal != und einmal == nicht zurecht?

 

[xyfreeman]

Ich sehe gerade, Java beachtet nur den Code aus dem letzten Block. Heh? Habe ich etwas mit den If's falsch gemacht?

 

[Der Müde Joe]

Habe ich etwas mit den If's falsch gemacht?

Im ersten Fall würd ich noch ein && aus dem & machen....
Java macht da keine Fehler. Es gibt 4 möglichkeiten und nur eine kann stimmen:

public static void main(String[] args) throws Exception {
	Object o = new Object();
	Object nullO = null;

	if (o == null && nullO != null) {
		System.out.println("false");			
	}
	if (o == null && nullO == null) {
		System.out.println("false");			
	}
	
	if (o != null && nullO == null) {
		System.out.println("true");			
	}
	if (o != null && nullO != null) {
		System.out.println("false");			
	}
}

 

[xyfreeman]

Ahja, habe ich geändert. Auch zusätzlich den 3ten Fall eingefügt. Aber das Ergebnis ist das selbe.

Hier noch mal die geänderte Methode.

 public void delete(T x){ 
  
  Node<T> preNode = root;
  Node<T> actNode = root;
  actNode = find(x);							// Findet aktuellen (zu löschenden Knoten)
  preNode = preFind(x);							// Findet den davorliegenden
  
    if(isInTree(x)){	
      if(actNode.getLeft().getItem() == null && actNode.getRight().getItem() == null){ 		// 1.Fall
        System.out.println("Erster Fall läuft");
        size--;
        if(x.compareTo(preFindGetItem(x)) < 0){
          preNode.setLeft(null);
        }
        else if (x.compareTo(preFindGetItem(x)) > 0){
          preNode.setRight(null);
        }
      }
    }
    if(isInTree(x)){  
      if(actNode.getLeft().getItem() == null && actNode.getRight().getItem() != null){		// 2.Fall
        System.out.println("Zweiter Fall läuft A");
        size--;
        if(x.compareTo(preFindGetItem(x)) < 0){												// actNode ist links (gesehen von preNode)
          preNode.setLeft(actNode.getRight());												// und Nachfolger rechts
        }
        else if (x.compareTo(preFindGetItem(x)) > 0){										// Nachfolger links
          preNode.setLeft(actNode.getLeft()); }
      }
    }
    if(isInTree(x)){
      if(actNode.getLeft().getItem() != null && actNode.getRight().getItem() == null){ 		// actNode ist rechts (gesehen von preNode)
        System.out.println("Zweiter Fall läuft B");
        size--;
        if(x.compareTo(preFindGetItem(x)) < 0){												// und Nachfolger rechts
          preNode.setRight(actNode.getRight());  }
        else if (x.compareTo(preFindGetItem(x)) > 0){										// Nachfolger links
          preNode.setRight(actNode.getLeft());       }
      }
    }
    if(isInTree(x)){																		// 3. Fall
      if(actNode.getLeft().getItem() != null && actNode.getRight().getItem() != null){		// Sucht Linkes oder Rechts
        System.out.println("Dritter Fall läuft");											// Teilbaum Maximum oder Minimum
        size--;
        if(actNode.getItem().compareTo(root.getItem()) < 0 ){								// Und ersetzt x durch dieses
          actNode.setItem(leftMax());														// Löscht danach dieses Max/Min
          delete(leftMax());																// Wenn x = root
        }																					// Dann wird rechtes Min
        else if(actNode.getItem().compareTo(root.getItem()) > 0 ){							// genommen
          actNode.setItem(rightMin());
          delete(rightMin());
        }
        else{
         actNode.setItem(rightMin());
         delete(rightMin());
        }
      }  
    }   
  }

Ich muss ehrlich sagen, ich habe keine Ahnung. Und ich sitze jetzt schon verdammt lange davor :-/
Ich geb's auf.

 

[Marco13]

Wenn du nicht aufgeben würdest, würdest du systematisch versuchen, rauszufinden, was dort schiefläuft. Z.B. mit

public void delete(T x){
 
  Node<T> preNode = root;
  Node<T> actNode = root;
  actNode = find(x);                     // Findet aktuellen (zu löschenden Knoten)
  preNode = preFind(x);                     // Findet den davorliegenden
 
  System.out.println("Deleting "+x);
  System.out.println("isInTree(x) "+isInTree(x));
  System.out.println("actNode.getLeft().getItem() "+actNode.getLeft().getItem());
  System.out.println("actNode.getRight().getItem() "+actNode.getRight().getItem());

    if(isInTree(x)){   
      if(actNode.getLeft().getItem() == null && actNode.getRight().getItem() == null){       // 1.Fall
        System.out.println("Erster Fall läuft"); 
     ....

oder es in einem Debugger angucken.