Binäre Bäume

[evil]

Hallo.
Ich habe ein Problem. Und zwar: möchte ich ein binären Baum implementieren, der 2 generische Implementierungen mit 2 Klassen besitzt.

Nun brauch ich ja zB eine Klasse Tree für die Elemente eines bestimmten Types. Und dann eine Klasse die die Typen über die Knoten verwaltet.

Leider weiß ich nicht genau, was nun in die Klassen hinein muss.Vielleicht kann man mir dort helfen.
Viele dank.

 

[Landei]

Ungefähr so...

public class Tree<E extends Comparable<E>> {
   private Node<E> root = null;

   public void add(E e) {
       if(root == null) {
          root = new Node<E>(e);
       } else {
          root.add(e);
       }
   }
   ...
}


public class Node<E extends Comparable<E>> {
   private Node<E> left = null;
   private Node<E> right = null;
   private E e;
   public Node(E e) {
      this.e = e;
   }
   public void add(E e) {
      switch((int)Math.signum(this.e.compareTo(e))) {
      case 0 : return; //haben wir schon
      case 1 : if (left == 0) left = new Node(e) else left.add(e); return;
      case -1 : if (right == 0) right = new Node(e) else right.add(e); return;
      }
   }
   ...
}

 

[evil]

Hey.. Und wo die "..." sind, beschreib ich meine Methoden wie der Baum verarbeitet wird? Also als Preorder, Inorder,...?

 

[newbie2009]

Hey.. Und wo die "..." sind, beschreib ich meine Methoden wie der Baum verarbeitet wird? Also als Preorder, Inorder,...?

ja genau hier is ja nur die methode zum hinzufügen von knoten
dann implementierst noch halt was dein herz so begehrt

z.b elemente entfernen oder baum ausgeben preorder oder wie du halt möchtest

 

[evil]

public class Tree<E extends Comparable<E>> {
   private TreeNode<E> root = null;
 
   public void add(E e) {
       if(root == null) {
          root = new TreeNode<E>(e);
       } else {
          root.add(e);
       }
   }
   ...
}
 
 
public class TreeNode<E extends Comparable<E>> {
   private TreeNode<E> left = null;
   private TreeNode<E> right = null;
   private E e;
   public Node(E e) {
      this.e = e;
   }
   public void add(E e) {
      switch((int)Math.signum(this.e.compareTo(e))) {
      case 0 : return; //haben wir schon
      case 1 : if (left == 0) left = new Node(e) else left.add(e); return;
      case -1 : if (right == 0) right = new Node(e) else right.add(e); return;
      }
   }
   
   public void traversePreorder() {
   	   if (e == null) 
   	   	   return;
   	   System.out.print("  " + e);
   	   left.traversePreorder();
   	   right.traversePreorder();
   }
   
   public void traverseInorder() {
   	   if (e == null)
   	   	   return;
   	   left.traverseInorder();
   	   System.out.print(" " + e);
   	   right.traverseIndorder();
   }
   
   public void traversePostorder() {
   	   if (e == null)
   	   	   return;
   	   left.traversePostorder();
   	   right.traversePostorder();
   	   System.out.print(" " + e);
   }
   
}

in etwa so?

 

[newbie2009]

hehe ja in etwa

 

[bipolar minds]

Hey, hätte nochmal ein problem bzgl. Preorder und Inorder..
Ich muss zwei Methoden

public String getInOrder_iterativ() {
	}

public String getPreOrder_iterativ() {
	}

implementieren, welche den Inhalt des Baumes iterativ(!) in inorder und preorder
in einem String ausgeben... das ganze soll mittels eines Stacks geschehen...
Hab leider überhaupt keine ahnung was mir der stack daei bringen soll und wie
ich das am besten realisieren kann.. wäre echt dankbar für einen vorschlag?
gruß tobi

 

[bipolar minds]

bräuchte eigtl. nur einen hinweis wie ich den stack nutzen kann, wäre ech supernett