binären Baum aus verzeigerter Liste ausgeben

[hawkeye78]

Hallo,

ich hoffe ich bin mit meiner Frage hier das richtige Unterforum zu erwischen, falls nicht möchte ich darum bitte, meinen Beitrag entsprechend umzustellen.
Mein Problem ist nun das ich in den letzten Tagen an einem Binären Baum gebasteltet habe der auf eine verzeigerte Liste aufsetzt. Als Grundstruktur existiert im moment folgender Aufbau, hierbei setzt sich ein Knoten aus dem gespeicherten Datum, sowie dem Zeiger auf das nächste Linke bzw. das nächste Rechte Kind zusammen:

Das einfügen, löschen sowie suchen funktioniert, allerdings scheitere ich im moment an einer vernünftigen und einfachen Ausgabe (in der DOS-Box reicht völlig ... ). Ich wäre daher über einen kleinen Hinweis wie ich dieses Problem anfassen könnte sehr dankbar.
Viele Grüsse
Dan

 

[bambi]

Ist irgendwie schwierig zu sagen, wenn man net weiss wie Du's programmiert hast.

Wo genau ist denn Dein Problem? Weisst Du nicht wie Du es darstellen sollst? Weisst Du nicht wie Du durch den Baum
gehen musst, um ihn darzustellen? Weisst Du nicht, wie Rekursion funktioniert? ... Woran genau liegt's? Wenn's an der
Programmierung scheitert, dann poste doch einfach mal ein bissl Code. :wink:

 

[hawkeye78]

Hallo Bambi,

zunächst einmal vielen Dank für dein Posting. Ich weiß nicht so recht wie ich den Baum möglichst gut Anfasse damit ich die Werte ausgegeben bekomme Im Moment hat mein Quellcode folgenden Aufbau

class Baum
{
Knoten first=null;     // Referenz auf die Wurzel

public void setFirst(Knoten e)

public void search(int i)

public void insert(int i)

public void delete(int i)

class Knoten
{
int wert=0;
Knoten NextLeft=null;
Knoten NextRicht=null;

// Set und Get Methoden um Setzen und Auslesen der Werte....
}
}

Ich hänge eigentlich ins besondere an der Stelle, wie ich nun wirklich den Verlauf des Baumes folgen kann um daraus eine einigermaßen brauchbare Ausgabe zu produzieren.
Ich möchte mich auf jeden Fall noch einmal für dein Posting bedanken.
Viele Grüsse
Dan

 

[bambi]

Also wie gesagt - Rekursion waere schon mal kein schlechter Anfang. Du kannst das aber auch ohne loesen - je nachdem
wie's am Ende aussehen soll...

Falls Du eine richtige Baumstruktur - so wie im Bild darstellen willst, wuerde ich ohne Rekurstion und vielleicht mit einem
Vector oder sowas arbeiten.

Hol' Dir einfach das erste Objekt und gib es aus.
Dann holst Du dir die Kinder und zeigst sie an.
Die Kinder wuerde ich irgendwo in einem Vector ablegen.
Dann holst Du deren Kinderelemente und zeigst diese an...
...
solange bis Du alle Elemente im Baum durch hast.

Und uebrigens :wink:

Knoten NextLeft=null;
//Knoten NextRicht=null; 
Knoten NextRight=null;

 

[Beni]

Hm, ich weiss nicht ob es vernünftig und einfach ist, aber ich hab in einem älteren Code von mit noch dies gefunden (habs ein bisschen auf dein Problem angepasst):

import java.awt.Color;
import java.awt.Dimension;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.util.ArrayList;
import java.util.List;

import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JScrollPane;

public class TreePaint extends JPanel{
    private FontMetrics metrics;
    private Node root = new Node( "root" );
    
    public static void main( String[] args ) {
        JFrame frame = new JFrame();
        frame.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE );
        frame.add( new JScrollPane( new TreePaint() ));
        frame.setBounds( 20, 20, 800, 600 );
        frame.setVisible( true );
    }
    
    public TreePaint(){
        metrics = getFontMetrics( getFont() );
        
        randomAdd( root, (int)(Math.random() * 2 + 3), 1 );
    }
    
    private void randomAdd( Node node, int count, int depth ){
        if( depth > 6 )
            return;
        
        for( int i = 0; i < count; i++ ){
            Node next = new Node( depth + " : " + i );
            node.addChild( next );
            randomAdd( next, (int)(Math.random() * 4), depth+1 );
        }
    }
    
    @Override
    public Dimension getPreferredSize() {
        Dimension size = root.getSize();
        return new Dimension( size.width + 40, size.height + 40 );
    }
    
    @Override
    public void paint( Graphics g ) {
        Dimension size = root.getSize();
        g.setColor( Color.WHITE );
        g.fillRect( 0, 0, getWidth(), getHeight() );
        g.setColor( Color.BLACK );
        g.setFont( getFont() );
        root.paint( g, getWidth()/2 - size.width/2, 20 );
    }
    
    private class Node{
        private String value;
        private List<Node> children = new ArrayList<Node>();
        private Dimension size;
        
        public Node( String value ){
            this.value = value;
        }
        
        public void setValue( String value ) {
            this.value = value;
            size = null;
        }
        
        
        public void addChild( Node node ){
            children.add( node );
            size = null;
        }
        
        public void removeChild( Node node ){
            children.remove( node );
            size = null;
        }
        
        public Dimension getSize(){
            if( size != null )
                return size;
            
            Dimension text = new Dimension(
                    metrics.stringWidth( value ) + 20,
                    metrics.getHeight() + 10
            );
            
            if( children.isEmpty() )
                return text;
            
            int width = 0;
            int height = 0;
            
            for( Node child : children ){
                Dimension size = child.getSize();
                width += size.width;
                height = Math.max( height, size.height );
            }
            
            text.width = Math.max( text.width, width );
            text.height += height + 5;
            
            size = text;
            return size;
        }
        
        public void paint( Graphics g, int x, int y ){
            Dimension size = getSize();
            g.drawString( value, x+10+size.width/2-metrics.stringWidth( value )/2,
                    y+5+metrics.getAscent() );
            
            int childX = x;
            for( Node child : children ){
                Dimension childSize = child.getSize();
                g.drawLine( x+10+size.width/2, y+5+metrics.getHeight(),
                        childX +10+ childSize.width/2, y+25+metrics.getHeight() );
                child.paint( g, childX, y+20+metrics.getHeight() );
                childX += childSize.width;
            }
        }
    }
}

Vielleicht kannst du da was rausnehmen.
P.S. Java 1.5 wird benötigt.

 

[PyroPi]

Hallo,

ich hab kürzlich auch eine Implementierung für einen Binären Baum in Java geschrieben. Für Debug-Ausgaben in der Konsole gab's zwei toString-Implementierungen: die Standard-Implementierung von Object (bei größeren Bäumen sehr unübersichtlich, dafür ohne Zeilenumbrüche) und eine Methode, die den Baum hierarchisch übersichtlicher darstellt.

Den Code hab ich jetzt nicht weiter verändert, daher kurz die erforderlichen Attribute der Klasse:

	private BinaryTree left;	// Linker Unterbaum
	private BinaryTree right;	// Rechter Unterbaum
	private Object item;		// Knoteninhalt
	
	private static int dist;

und die beiden toString-Methoden:

	public String toString() {
		String str = new String();
		
		str = "(<" +
			(left==null ? "." : left.toString()) + ">" +
			(item==null ? "<null>" : item.toString()) + "<" +
			(right==null ? "." : right.toString()) + ">)";  
		
		return str;
	}


	public String toNiceString() {
		return toNiceString(0);
	}

	private String toNiceString(int dist) {
		String str = new String();
		
		for (int i=0; i<dist-1; i++) str += "  |  ";
		
		if (dist>0) str += "  |- ";
		str += "Item: " + (item==null ? "<null>" : item.toString()) + "\n";
		
		if (left == null) {
			for (int i=0; i<dist; i++) str += "  |  ";
			str += "  |- <null>\n";
		}
		else str += left.toNiceString(dist+1);

		if (right == null) {
			for (int i=0; i<dist; i++) str += "  |  ";
			str += "  |- <null>\n";
		}
		else str += right.toNiceString(dist+1);

		return str;
	}

Mußt du noch ein wenig auf deinen Code anpassen.

Grüße,

PyroPi