Binärbaum implementieren

[Smartie86]

Servus. ich muss einen Binärbaum in Java implementieren und diesen mit Generics mit verschiedenen Schlüsseln kompatibel machen.

Meine Problem ist der obligatorische größer/kleiner-Vergleich beim Einfügen/Löschen eines neuen Knotens.
Bei generischen Schlüsseln ist < und > ja nicht definiert.

Ich habe leider keine Ahnung wie man generische Schlüssel auf Größenunterschiede vergleichen kann :/

Ich hatte alles erstmal als int-Baum ausgelegt um überhaupt mal was machen zu können, und nun weiß ich leider mit den generischen Schlüsseln nicht weiter.
Ich schätze mal, daß man da irgndeine Art von comparator benutzen muss, aber ich hab ehrlich gesagt keine Ahnung davon und werde aus der Java Api dafür nicht ganz schlau
Hilfe

// Meine Knotenklasse

public class Node<E>
{
	
	Node<E> left;
	Node<E> right;
	Node<E> parent;
	E value;
	
	public Node (E val, Node<E> parent)
	{
		left = right = null;
		this.parent = parent;
	}
	
	public E getValue()
	{
		return value;
	}
}




// Meine Baumklasse

import java.util.*
public class Tree<E> implements Iterable<E>
{

	Node<E> root = null;
	
	enum Order {Preorder, Postorder, Inorder};
	
	private Order order = Order.Preorder;
	
	void setOrder (Order x)
	{ 
		order = x;
	}
	
	.....
	
	public void add(E val)
	{
		if ( root == null ) root = new Node<E> (val, null ) ;
		else add ( root , val ) ;
	}
	
	public void add (Node<E> k, E val)
	{
		if (val < k.value)
		{
			if (k.left == null) k.left = new Node<E>(val, k);
			else add(k.left, val);
		}
		else
		{
			if (k.right == null) k.right = new Node<E> (val, k);
			else add(k.right, val);
		}
	}
	
        ......


	public void delete (E val)
	{
		delete(root,val);
	}
	
	
	public void delete (Node<E> k, E val)
	{
		Node<E> right;
		Node<E> preRight;
		if (k != null)
		{
			if (k.value == val)
			{
				if (k.right == null && k.left == null) k = null;
				else
				{
					if (k.left == null) k = k.right;
					else
					{
						if (k.right == null) k = k.left;
						else
						{
							right = k.left;
							preRight = null;
							while (right.right != null)
							{
								preRight = right;
								right = right.right;
							}
							if (preRight != null)
							{
								preRight.right = right.left;
								right.left = k.left;
							}
							right.right = k.right;
							k = right;
						}
					}
				}

			}
			else
			{
				if (val > k.value)
				{
					delete(k.right, val);
				}
				if (val < k.value)
				{
					delete(k.left, val);
				}
			}
		}		
	}
	
	

}



// meine Main-Klasse


public class TreeMain 
{

	/**
	 * @param args
	 */
	public static void main(String[] args) 
	{
		// TODO Auto-generated method stub
		Tree<Integer> t = new Tree<Integer>();
		t.setOrder(Order.Preorder);
	}

}

Ich habe noch ein kleines Problem dessen ursache mir nicht ganz klar ist: in der main Klasse bei t.setOrder(Order.Preorder) sagt mir eclipse Order cannot be resolved, aber es ist definitiv in der Baumklasse definiert, ich versteh es nicht


mfg
Smartie

 

[Smartie86]

ich hab das jetzt mal so implementiert, aber ob das stimmt müsstet ihr mir sagen. und den Fehler mit dem "order" in der Main finde ich leider nach wie vor nicht

public class Tree<E extends Comparable> implements Iterable<E>, Comparator<E>
{
	
	public int compare(E o1, E o2) {
        return o1.compareTo(o2);


    }

 

[Gast]

t.setOrder(t.Order.Preorder)

mach das innere enum static, dann klappts auch ohne Tree objekt.

 

[Smartie 86]

Bitte bitte bitte hilf mir mal jemand, das mit dem Comparator klappt natürlich garnicht, ich bekomme nur Fehler

Hilfe

 

[Guest]

public class Tree<E extends Comparable> implements Iterable<E>, Comparator<E>

iieeeks was ist denn das? Naja aber jeder hat ja mal klein angefangen

1. Comparable ist ein Interface
2. Du willst doch die Nodes Vergleichen und nicht den Baum, oder? => Comparable in "Node" implementieren!
3. die Methode compareTo musst du selbst implementieren, also sowas wie "Knoten a ist kleiner als Knoten B wenn value von A kleiner ist"
4. Warum implementierst du Iterable? Bzw. wo ist die Implementation?
5. Was ist E?[/code]

 

[Smartie86]

2. Du willst doch die Nodes Vergleichen und nicht den Baum, oder? => Comparable in "Node" implementieren!

Das problem ist, daß der Baum für beliebige Schlüssel nutzbar sein soll. Was mach ich jetzt Wenn jemand auf die idee kommt ein Objekt wie z.B. "Buch" zu übergeben. Sowas kann ich doch unmöglich voraussehen, geschweigedenn Vergleichsmethoden dazu im Vorraus implementieren.

3. die Methode compareTo musst du selbst implementieren, also sowas wie "Knoten a ist kleiner als Knoten B wenn value von A kleiner ist"

Ok.

4. Warum implementierst du Iterable? Bzw. wo ist die Implementation?

	public enum Order {Preorder, Postorder, Inorder};
	
	private Order order = Order.Preorder;

public Iterator<E> iterator()
	{ 
    	return genArrayList().iterator();	
	}   
	
	public ArrayList<E> genArrayList()
	{
	   	 ArrayList<E> list = new ArrayList<E>(countNodes());
	   	 switch (order)
	   	 {
	   	   case Preorder:   preOrder(list);   break;
	   	   case Postorder:  postOrder(list);  break;
	   	   case Inorder:    inOrder(list);    break;
	   	 }
	   	 return list;
	}

5. Was ist E

Ein Platzhalter für den späteren Typus? Oder ist das auch falsch?

Ich seh schon, ich hab nicht die geringste Ahnung was ich hier tue.

 

[Guest]

Hab nicht viel Zeit (hab auch deinen ersten post noch immer nicht ganz durchgelesen, sorry), daher nur kurz:
Erzwinge als Typ "Compareable", also statt E => Compareable
Damit ist sichergestellt das alle Klassen die verendet werden Compareable implementieren, du kannst dann also unbesorgt compareTo aufrufen
Schwierig wirds nur wenn mehrere VERSCHIEDENE Klassen gleichzeitig verwendet werden sollen, denn wie vergleicht man Buch A mit Fernseher B? Was ist größer bzw. kleiner?