Binärer Suchbaum


#1
Hallo,
Wir sollen einen binären Suchbaum erzeugen.
Folgende Klassen habe ich:
Benutzerverwaltung
Code:
public class Benutzerverwaltung {
   
private BinarySearchTree<Benutzerprofil> benutzerBaum;

public Benutzerverwaltung() {

 benutzerBaum = new BinarySearchTree<Benutzerprofil>();
}

public void neuenNutzerAnlegen(String pBenutzername, String pPw) {
Benutzerprofil b = new Benutzerprofil(pBenutzername, pPw);

benutzerBaum.insert(b);
}

public void nutzerLoeschen(String pBenutzername, String pPw) {
 Benutzerprofil b = new Benutzerprofil(pBenutzername, pPw);
 benutzerBaum.remove(b);
 }

 public boolean profilVorhanden(String pBenutzername) {
   
 Benutzerprofil b = new Benutzerprofil(pBenutzername, "");
 Benutzerprofil ergebnis = benutzerBaum.search(b);
if(ergebnis != null) {
   
 return true;
}
else return false;

 }
 }
Benutzerprofil
Code:
public class Benutzerprofil implements ComparableContent<Benutzerprofil>

{
   
private String benutzername, pw;
   

/**
     * Konstruktor für Objekte der Klasse Benutzerprofil
     */

public Benutzerprofil(String pBenutzername, String pPw)
   
{
       
benutzername = pBenutzername;
       
pw = pPw;
   
}

public String getBenutzername()
   
{
       
 return benutzername;
   
}
   
   
public boolean isGreater(Benutzerprofil pProfil)
   
{

        return this.getBenutzername().compareTo(pProfil.getBenutzername())>0;
   
}
 
 
   
public boolean isLess(Benutzerprofil pProfil)
   
{
        return this.getBenutzername().compareTo(pProfil.getBenutzername())<0;
   
}
   
   
public boolean isEqual(Benutzerprofil pProfil)
   
{
       
return this.getBenutzername().compareTo(pProfil.getBenutzername())==0;
   
}


}
Und die Main Methode, wo der Suchbaum ertsellt werden soll:
Code:
public class SUCHBAUM {

   static void main(String[] args) {
       // TODO Auto-generated method stub

       
       Benutzerprofil yoki33 = new Benutzerprofil("yoki33", "yok");
       Benutzerprofil udo86 = new Benutzerprofil("udo86", "udo");
       Benutzerprofil susi81 = new Benutzerprofil("susi81", "susi");
       Benutzerprofil jan62 = new Benutzerprofil("jan62", "jan");
       Benutzerprofil michel93 = new Benutzerprofil("michel93", "michel");
       Benutzerprofil tina90 = new Benutzerprofil("tina90", "tina");
       Benutzerprofil Azrael11 = new Benutzerprofil("Azrael11", "Azrael");
       Benutzerprofil Ezekiel23 = new Benutzerprofil("Ezekiel23", "Ezekiel");
       
   
   
       BinarySearchTree<Benutzerprofil> benutzerBaum;
       
       benutzerBaum = new BinarySearchTree<Benutzerprofil>();
       
       benutzerBaum.insert(yoki33);
       benutzerBaum.insert(udo86);
       benutzerBaum.insert(susi81);
       benutzerBaum.insert(jan62);
       benutzerBaum.insert(michel93);
       benutzerBaum.insert(tina90);
       benutzerBaum.insert(Azrael11);
       benutzerBaum.insert(Ezekiel23);
       
       
   //   System.out.println(tina90.getBenutzername());
       
       while( !benutzerBaum.isEmpty()) {                                                   //Ganzer Baum Ausgeben                                                                                                //PROBLEM 1
           System.out.println(benutzerBaum.getBenutzername());
       }               
       
       
   
       
       benutzerBaum.remove(yoki33);                                       //löschen     PROBLEM 2
       benutzerBaum.search(yoki33);                                   //suchen            PROBLEM 3
   

       
   }
}
Bei der Main Methode gibt es drei Probleme:
1.) In der while-Schleife (der ganze Baum soll ausgegeben werden) ist getBenutzername() ein Fehler. Wie änder ich es, damit es funktioniert?
2.) Ich lösche eine Person aus dem Baum. Sie ist dennoch noch da, wen ich sie aufrufe. Wieso? Wie kann ich es beheben?
3.) Ist die Suche -benutzerBaum.search(yoki33);- so richtig? Beim ausführen erscheint kein Ergebnis in der Konsole.

Hoffe jemand hier kann mir helfen :D
VG Max
 
#2
Hab die Klasse BinarySearchTree vergessen...
Die Klasse BinarySearchTree
Code:
public class BinarySearchTree<ContentType extends ComparableContent<ContentType>> {

   /* --------- Anfang der privaten inneren Klasse -------------- */
   private class BSTNode<CT extends ComparableContent<CT>> {
     
       private CT content;
       private BinarySearchTree<CT> left, right;

       public BSTNode(CT pContent) {
           // Der Knoten hat einen linken und rechten Teilbaum, die
           // beide von null verschieden sind. Also hat ein Blatt immer zwei
           // leere Teilbaeume unter sich.
           this.content = pContent;
           left = new BinarySearchTree<CT>();
           right = new BinarySearchTree<CT>();
       }
       
   }

   /* ----------- Ende der privaten inneren Klasse -------------- */

   private BSTNode<ContentType> node;

   
   public BinarySearchTree() {
       this.node = null;
   }

   
   public boolean isEmpty() {
       return this.node == null;
   }

 
   public void insert(ContentType pContent) {
       if (pContent != null) {
           if (isEmpty()) {
               this.node = new BSTNode<ContentType>(pContent);
           } else if (pContent.isLess(this.node.content)) {
               this.node.left.insert(pContent);
           } else if(pContent.isGreater(this.node.content)) {
               this.node.right.insert(pContent);
           }
       }
   }

 
   public BinarySearchTree<ContentType> getLeftTree() {
       if (this.isEmpty()) {
           return null;
       } else {
           return this.node.left;
       }
   }

 
   public ContentType getContent() {
       if (this.isEmpty()) {
           return null;
       } else {
           return this.node.content;
       }
   }

 
   public BinarySearchTree<ContentType> getRightTree() {
       if (this.isEmpty()) {
           return null;
       } else {
           return this.node.right;
       }
   }
   public void remove(ContentType pContent) {
       if (isEmpty()) {
           // Abbrechen, da kein Element zum entfernen vorhanden ist.
         return;
       }
       
       if (pContent.isLess(node.content)) {
           // Element ist im linken Teilbaum zu loeschen.
           node.left.remove(pContent);
       } else if (pContent.isGreater(node.content)) {
           // Element ist im rechten Teilbaum zu loeschen.
           node.right.remove(pContent);
       } else {
           // Element ist gefunden.
           if (node.left.isEmpty()) {
               if (node.right.isEmpty()) {
                   // Es gibt keinen Nachfolger.
                   node = null;
               } else {
                   // Es gibt nur rechts einen Nachfolger.
                   node = getNodeOfRightSuccessor();
               }
           } else if (node.right.isEmpty()) {
               // Es gibt nur links einen Nachfolger.
               node = getNodeOfLeftSuccessor();
           } else {
               // Es gibt links und rechts einen Nachfolger.
               if (getNodeOfRightSuccessor().left.isEmpty()) {
                   // Der rechte Nachfolger hat keinen linken Nachfolger.
                   node.content = getNodeOfRightSuccessor().content;
                   node.right = getNodeOfRightSuccessor().right;
               } else {
                   BinarySearchTree<ContentType> previous = node.right
                           .ancestorOfSmallRight();
                   BinarySearchTree<ContentType> smallest = previous.node.left;
                   this.node.content = smallest.node.content;
                   previous.remove(smallest.node.content);
               }
           }
       }       
   }

 
   public ContentType search(ContentType pContent) {
       if (this.isEmpty() || pContent == null) {
           // Abbrechen, da es kein Element zu suchen gibt.
           return null;
       } else {
           ContentType content = this.getContent();
           if (pContent.isLess(content)) {
               // Element wird im linken Teilbaum gesucht.
               return this.getLeftTree().search(pContent);
           } else if (pContent.isGreater(content)) {
               // Element wird im rechten Teilbaum gesucht.
               return this.getRightTree().search(pContent);
           } else if (pContent.isEqual(content)) {
               // Element wurde gefunden.
             return content;               
           } else {   
             // Dieser Fall sollte nicht auftreten.
               return null;
           }
       }
   }

   /* ----------- Weitere private Methoden -------------- */

 
   private BinarySearchTree<ContentType> ancestorOfSmallRight() {       
       if (getNodeOfLeftSuccessor().left.isEmpty()) {
           return this;
       } else {
           return node.left.ancestorOfSmallRight();
       }
   }

   private BSTNode<ContentType> getNodeOfLeftSuccessor() {
       return node.left.node;
   }

   private BSTNode<ContentType> getNodeOfRightSuccessor() {
       return node.right.node;
   }

}
 

HonniCilest

Erfahrenes Mitglied
#3
1. Nicht dein Baum besitzt die Methode, sondern ein Profil. Du musst die Methode also schon auf einem Speziellen Profil aufrufen.
2. Was meinst du sie ist noch da, ist sie noch im Baum??
3. Du suchst yoki nachdem du ihn gelöscht hast?!
 

HonniCilest

Erfahrenes Mitglied
#5
Aber du sagt doch beim Search, dass kein Ergebnis erscheint. Woher weißt du dann, dass er noch da ist?


Bei ersten meine ich...

Java:
System.out.println(benutzerBaum.getBenutzername());
benutzerBaum ist doch aber ein BinarySearchTree. Die Methode getBenutzername() gehört jedoch zur Klasse Benutzerprofil. Du musst dir also entweder ein bestimmtes Benutzerprofil aus dem Baum holen oder eben für BinarySearchTree die Methode auch definieren.
 

Neue Beiträge