Binärer Suchbaum

[Exa]

Hallo @all.
Ich muss für mein Programmierpraktikum ( bin Infostudent im ersten Semester ) ein Binären Suchbaum programmieren und ihn dann wahlweise inorder, preorder oder postorder ausgeben. Das einfügen klappt gut. Aber ich grübel hin und her wie ich am dümmsten diesen baum dann ausgebe.. in-,pre- bzw postorder und komme nicht drauf. Wäre für nen denkanstoss dankbar. Quelltext will ich allerdings nicht.. möchte das schon selbst programmieren.
Der Baum is ne zeigervekttet Liste wobei jedes Element immer auf das nächste rechte und linke zeigt und der Zeiger immer auf der Wurzel ist.

Bin für jede Idee dankbar.

So long

exa

 

[SlaterB]

wie gibts du denn überhaupt den Inhalt des Baumes in irgendeiner Ordnung aus?

das ist doch eine einfache Rekursion:
in jedem Baumknoten müssen prinzipiell drei Befehle gestartet werden:
gib linken Teilbaum aus
gib mich selbst aus
gib rechten Teilbaum aus,

je nach Reihenfolge dieser drei Befehle dürfte sind die Order ergeben?!

 

[Exa]

Naja. Wenn ich den InOrder ausgeben will muss ich mit dem Knoten im Baum ganz Links unten anfangen und dann alle Knoten von links nach rechts der selben ordung ausgeben. Dann quasi eine ordnung runter und alle Knoten von links nach rechts ausgeben etc bis Wurzel.. dann das selbe spiel mit dem rechten Baum. Das problem.. bzw mein Problem ist... ich kann ja auf dem Baum nur vorwärts laufen weil es keinen Zeiger gitb, der zurück zeigt. Die Knoten haben eine klasse bekommen die wir verwenden müssen ( die wurde uns so geben );

public class Student {
	
	public Student(int matrikel, String name) {
		this.matrikel = matrikel;
		this.name = name;
	}
	
	public int matrikel;
	public String name;
	
	public Student links;
	public Student rechts;
}

aber da gibt es keine option das ich für einen Studenten auch eine Ordung festlegen kann.

 

[Exa]

ach und wenn ich den baum dann rotieren lassen will, Zwecks dem Gleichgewicht würden ja auch alle ordnungen kaputt gehen. also muss das auch ohne gehen.
Bei dem Algorithmus für inorder renne ich so lang nach links bis nachfolger null wird und geb ihn aus.. das is ja kein thema... aber dann muss ich den rechten vom vorgänger ausgeben bzw wenn der unterknoten.. etc... keine ahnung :?: :cry:

 

[Guest]

Hier ein einfaches Beispiel

public class BinTree
{
  static class Node
  {
    public Node left;
    public Node right;
    public String name;

    public Node(String name, Node left, Node right)
    {
      this.name  = name;
      this.left  = left;
      this.right = right;
    }
  }

  public static void preOrder(Node node)
  {
    System.out.print(node.name);
    if(node.left != null)
      preOrder(node.left);
    if(node.right != null)
      preOrder(node.right);
  }

  public static void inOrder(Node node)
  {
    if(node.left != null)
      inOrder(node.left);
    System.out.print(node.name);
    if(node.right != null)
      inOrder(node.right);
  }

  public static void postOrder(Node node)
  {
    if(node.left != null)
      postOrder(node.left);
    if(node.right != null)
      postOrder(node.right);
    System.out.print(node.name);
  }

  public static void main(String argv[])
  {
    /*

         A
       /    \
      B      D
      \    /   \
       C  E     H
         / \   /
        F   G I

    */
    Node c = new Node("C", null, null);
    Node f = new Node("F", null, null);
    Node g = new Node("G", null, null);
    Node i = new Node("I", null, null);
    Node b = new Node("B", null, c);
    Node e = new Node("E", f, g);
    Node h = new Node("H", i, null);
    Node d = new Node("D", e, h);
    Node a = new Node("A", b, d);

    preOrder(a);
    System.out.println();
    inOrder(a);
    System.out.println();
    postOrder(a);
  }
}

 

[Exa]

Wollte zwar keinen quelltext aber das is insofern nicht so wild, das die ausgabe noch nicht ganz so ist wie sie sein soll wenn ich das für mein programm portiere.. hab also noch was zu knobeln ... auf jeden fall vielen lieben dank für die evtl. arbeit falls du es eben geschrieben hast und vieeelen dank das das so fix ging.. is nen prima forum

ps : wenn hier mal nen admin vorbei rennt... macht nen haken :toll:

 

[Guest]

Zeichne am besten jeden Schritt auf, damit du auch verstehst, wie es funktioniert.

 

[JimBo]

Das Thema kommt mir grade ganz gelegen. Wie sieht es aus wenn ich ein Element wieder aus dem Baum löschen möchte. Ich habe es so probiert. Er läuft mit inorder solange durch bis er den passenden eintrag gefunden hat. Dann setzt er diesen auf null und somit müsste doch der gewünschte eintrag und alle seine kinder weg sein. ?? Ich bekomm dann aber leider eine NullPointerException. Wie kann ich verhindern, dass dies auftritt??