BinärBaum Hilfestellung

[newbie2009]

hey leute ich mache mich gerade an einem Binärbaum in java.
ich weiß es gibt , schon lösungen im Netz, aber ich möchte mir es selbst erarbeiten und hoffe, dass ihr mich mit Tipps auf dem Weg zur Lösung begleitet.Vielen dank im Voraus.
Ich habe bisher nur Baumknoten erstellt, was mir probleme zubereitet nun einen Baum zu konstruieren sprich noch nix durchsuchen nur einen aufzubauen.
Ich habe bisher versucht rekursiv vorzugehen aber irgendwie klappt es noch nicht.
Tipps?:rtfm:

class Baumknoten{
	
	
	private int  zeichen;
	private Baumknoten links, rechts;
	
	
	// erster Konstruktor falls nur ein knoten vorhanden ist 
		public Baumknoten(){
		links =null;
		rechts = null;
		zeichen = ((int)(Math.random()*100+1));
		}
	
	
	// falls weiter Knoten vorhanden sind
		public Baumknoten(int z, Baumknoten l, Baumknoten r){
			links = l;
			rechts = r;
			zeichen = z;
		}

public Object getZeichen()
{
return zeichen;
}
public Baumknoten getLinks()
{
return links;
}
public Baumknoten getRechts()
{
return rechts;

}

 

[Empire Phoenix]

Sieht doch soweit sinnvoll aus,

als hilfe mal eine methode zum anzeigen des baumes, du musst allerdings die methoden/klassen entsprechend anpassen,
arbeitet auch gleich mit rekursion und jeweils einer verzweigung in weitere rekursionen pro schritt.

Das ganze war ürsprünglich zum erzeugen von encodings mit dynamischer länge gedacht nach dem hoffmancode, auf nachfrage kann ich auch den rest posten.

	private void exportBinaryTree() {
		JFrame frame = new JFrame("KodierBaum");
		frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
		DefaultMutableTreeNode masterdescriptor = new DefaultMutableTreeNode(
				"Masternode total:" + this.masternode.getProbability());
		JTree tree = new JTree(masterdescriptor);
		frame.add(new JScrollPane(tree));
		addAllChilds(this.masternode, masterdescriptor);
		frame.pack();
		frame.setVisible(true);
	}

	private void addAllChilds(BinaryNode parent,
			DefaultMutableTreeNode descriptor) {
		BinaryNode nodea = parent.getChilda();
		if (nodea != null) {
			DefaultMutableTreeNode adescr = new DefaultMutableTreeNode(
					"ChildA P:" + nodea.getProbability() + " B:"
							+ nodea.getBitvalue() + " L:" + nodea.getLetter());
			descriptor.add(adescr);
			addAllChilds(nodea, adescr);
		}

		BinaryNode nodeb = parent.getChildb();
		if (nodeb != null) {
			DefaultMutableTreeNode bdescr = new DefaultMutableTreeNode(
					"ChildB P:" + nodeb.getProbability() + " B:"
							+ nodeb.getBitvalue() + " L:" + nodeb.getLetter());
			descriptor.add(bdescr);
			addAllChilds(nodeb, bdescr);
		}
	}

Ähnlich kann man dann zb auch die suche nach einem element veranstalten:

	private BinaryNode findNode(BinaryNode parent, char letter) {
		BinaryNode childa = parent.getChilda();
		if (childa != null) {
			if (childa.getLetter() == letter) {
				return childa;
			}
			BinaryNode testa = findNode(childa, letter);
			if (testa != null) {
				return testa;
			}
		}

		BinaryNode childb = parent.getChildb();
		if (childb != null) {
			if (childb.getLetter() == letter) {
				return childb;
			}
			BinaryNode testb = findNode(childb, letter);
			if (testb != null) {
				return testb;
			}
		}
		return null;
	}

 

[newbie2009]

hey danke empire_phoenix , aber um die visualisierung geht es im moment noch nicht

also meine idee war nun eine methode zu konstruieren , die den baum aufbaut.

void erstellen(int elemente,Baumknoten vorgänger){
	
	if(vorgänger==null|| elemente <0){
	System.out.println("abbruch");
	return ;	
	
	}
	
	Baumknoten neuerknoten = new Baumknoten();
	
	if(vorgänger.links==null&&elemente>0) {
		vorgänger.links=neuerknoten;
		
		elemente--;
		erstellen(elemente,neuerknoten);
		
		
	if(vorgänger.rechts==null&&elemente>0){
		Baumknoten bla = new Baumknoten();
		vorgänger.rechts=bla;
		elemente--;
		erstellen(elemente,bla);
	}
	}
	
	
	
	
}

Habe mir das nun so überlegt, dass ich angebe wieviele knoten eingefügt werden sollen(int elemente) und den vorgängerknoten, und dass dann der Baum aufgebaut wird.Also ich bekomme keine Fehlermeldungen aber ist der Ansatz überhaupt richtig ? und bekomme ich damit wirklich eine Baumstruktur ?
:rtfm:

 

[blawa]

Ich habe deinen Code getestet, und bekomme keine Exception.

Aber als kleine Anmerkung:
Du hängst alle Knoten immer and den Linken Knoten an.

Ich habe deinen Code kopiert, und in eine 2te Klasse die main gesteckt und folgendes Ausgeführt:

 public static void main(String[] args) {
        Baumknoten root=new Baumknoten();
        Baumknoten.erstellen(7, root);

        int cnt=0;
        while(root.getLinks()!=null) {cnt++;root=root.getLinks();}
        System.out.println(""+cnt);
    }

Da kommt als Output 7, also sind alle nur Links angehängt.
Als einzige Änderung habe ich "erstellen" statisch gemacht.

Du kannst das erstellen aber theoretisch mit einer Schleife durchlaufen, sodass du einen mehr oder weniger balancierten Baum bekommst.

mfg

 

[newbie2009]

Ich habe deinen Code getestet, und bekomme keine Exception.

Aber als kleine Anmerkung:
Du hängst alle Knoten immer and den Linken Knoten an.

Ich habe deinen Code kopiert, und in eine 2te Klasse die main gesteckt und folgendes Ausgeführt:

 public static void main(String[] args) {
        Baumknoten root=new Baumknoten();
        Baumknoten.erstellen(7, root);

        int cnt=0;
        while(root.getLinks()!=null) {cnt++;root=root.getLinks();}
        System.out.println(""+cnt);
    }

Da kommt als Output 7, also sind alle nur Links angehängt.
Als einzige Änderung habe ich "erstellen" statisch gemacht.

Du kannst das erstellen aber theoretisch mit einer Schleife durchlaufen, sodass du einen mehr oder weniger balancierten Baum bekommst.

mfg

Hey danke, versuch ma deine Schleife für get.Rechts(); da bekommst genauso viele elemente raus, also werden die theoretisch nicht nur links angehangen oder verstehe ich da was falsch
und wenn ich dann mit die werte ausgeben wollen würde und

System.out.println(wurzel.getRechts());

aufrufen würde, müsste deiner Theorie nach eine Nullpointerexception geworfen werden , wird aber nicht, aber trotzdem läuft da irgendetwas falsch ^^

 

[blawa]

nein Rechts sind keine 7 Elemente sondern 3.

Er ruft ja im ersten durchlauf das wie folgt auf:

(Root,7)

links == null also root.links=new();
zähler--; // Hier ist also zähler==6
rekursion(new(),6)

Aber jetzt kommt er zur rechten seite, und macht folgendes:
zähler--;
rekursion(new(),5)

also hast du einen aufteigenden Baum von links nach rechts

mfg

 

[newbie2009]

nein Rechts sind keine 7 Elemente sondern 3.

Er ruft ja im ersten durchlauf das wie folgt auf:

(Root,7)

links == null also root.links=new();
zähler--; // Hier ist also zähler==6
rekursion(new(),6)

Aber jetzt kommt er zur rechten seite, und macht folgendes:
zähler--;
rekursion(new(),5)

also hast du einen aufteigenden Baum von links nach rechts

mfg

aber das muss doch so sein , denn wenn die anzahl der elemente ungerade ist, dann kann es halt einen unvollständigen baum geben oder nich ?

oh man hat jemand vll ne anderen vorschlag für den rekursiven aufbau des baums , irgendetwas stimmt da nicht:autsch:

 

[blawa]

Naja, wenn der Baum balanciert sein soll (also max 1 Ebene differenz), muss man rotate Funktionen verwenden.
Dass nennt man dann einen AVL Baum.

Deine Funktion baut zwar einen Baum, aber der Parameter "elemente" gibt hald die tiefste Ebene an.

Mit einer rekursiven Funktion einen B-Baum aufbauen, der die übergeben Anzahl an Element hat, ist schwer.

Ich kenne den Aufbau-Algorithmus nur als Schleife, hier der Pseudocode, falls es dir hilft (Der Baum ist gewichtet):

einfügen(knoten root,knoten q) {
knoten r,p;
r=NULL;
p=root;
solange(p!=null) {
r=p;
 if(q.key<p.key) {
  p=p.left;
} else {
 p=p.right;
}
}
q.vorgänger=r;
q.left=null;
q.right=null;
if(r==null) {
 root=q;
} else {
 if(q.key<r.key) {
  r.left=q;
} else {
 r.right=q;
}
}
}

Hoffe das hilft dir

 

[newbie2009]

Naja, wenn der Baum balanciert sein soll (also max 1 Ebene differenz), muss man rotate Funktionen verwenden.
Dass nennt man dann einen AVL Baum.

Deine Funktion baut zwar einen Baum, aber der Parameter "elemente" gibt hald die tiefste Ebene an.

Mit einer rekursiven Funktion einen B-Baum aufbauen, der die übergeben Anzahl an Element hat, ist schwer.

Ich kenne den Aufbau-Algorithmus nur als Schleife, hier der Pseudocode, falls es dir hilft (Der Baum ist gewichtet):

einfügen(knoten root,knoten q) {
knoten r,p;
r=NULL;
p=root;
solange(p!=null) {
r=p;
 if(q.key<p.key) {
  p=p.left;
} else {
 p=p.right;
}
}
q.vorgänger=r;
q.left=null;
q.right=null;
if(r==null) {
 root=q;
} else {
 if(q.key<r.key) {
  r.left=q;
} else {
 r.right=q;
}
}
}

Hoffe das hilft dir

hey erstmal vielen dank
ja hast recht, mit elemente wird bei mir die tiefe angegeben , und nicht die anzahl der elemente , oh man so langsam bin ich am verzweifeln , hatte es mir leichter vorgestellt
habe zwar jetzt die klasse mit methoden bisscehn geändert kommt auch jetzt mit anzahl der elementen hin , aber ich glaube nicht , dass das an eine struktur des baums rankommt.:autsch:

import java.util.*;


class Baumknoten{
	
	
	private int  zeichen;
	private Baumknoten links, rechts;
	
	
	// erster Konstruktor falls nur ein knoten vorhanden ist 
		public Baumknoten(){
		links =null;
		rechts = null;
		this.zeichen =0;
		}
	
	
	// falls weiter Knoten vorhanden sind
		public Baumknoten(int z, Baumknoten l, Baumknoten r){
			links = l;
			rechts = r;
			zeichen = z;
		}

		public Baumknoten(int z){
			links = null;
			rechts = null;
			this.zeichen = z;
		}
		
		
		// getter Methoden 
public Object getZeichen(){
return zeichen;
}
public Baumknoten getLinks(){
return links;
}
public Baumknoten getRechts(){
return rechts;}

// setter Methoden 

public void setZeichen(int m){
this.zeichen=m;
}

public void setLinks(Baumknoten m){
this.links=m;
}
public void setRechts(Baumknoten m)
{
this.rechts=m;


}
static int kla= IO.readInt("bitte zahl eingeben ");

void erstellen(Baumknoten eingabe){

	if(eingabe==null){
		System.out.println("abbruch");
		return ;
	}
	
	if(eingabe.getLinks()==null&&kla>0){
		Baumknoten neu= new Baumknoten(1);
		eingabe.setLinks(neu);
		kla--;
		 if(eingabe.getRechts()==null&&kla>0){
			 Baumknoten neu2= new Baumknoten(2);
			 eingabe.setRechts(neu2);
			kla--;
			 erstellen(neu);
			 erstellen(neu2);
			 
		 }
	}
	
	
	
	
}

ich meine der erstellt nur die knoten , im linken teil der wurzel.
hat keiner einen vorschlag?