Java Binären Baum erzeugen

[XHotSniperX]

Hallo

Wie kann man am besten iterativ einen binären Baum erzeugen von der Höhe n? Die Werte in den Knoten können mal alle leer sein.

Sagen wir mal ich hab sowas:

class BinaryTreeNode
{
	private Object value;
	private BinaryTreeNode left;
	private BinaryTreeNode right;

	public BinaryTreeNode(Object o)
	{
		value = o;
		left = null;
		right = null;
	}

	public Object getValue() { return value; }
	public BinaryTreeNode getLeft() { return left; }
	public BinaryTreeNode getRight() { return right; }
	
	public void setValue(Object v) { value = v; }
	public void setLeft(BinaryTreeNode p) { left = p; }
	public void setRight(BinaryTreeNode p) { right = p; }
}

public class Blabla
{
	private static BinaryTreeNode root;
	int length;
	
	public static void generateTree()
	{
        root = new BinaryTreeNode(""); // die Knoten haben vorerst leere Werte
  
        }
}

mit generateTree möchte ich nun einen binären Baum der Höhe n erstellen. Wie kann ich denn ohne Rekursion einen Baum erzeugen? In die value Variable möchte ich einfach ("") rein tun. Also noch nichts. Einfach mal den Baum erstellen mit leeren Werten. Ne Idee?

 

[-Razzer-]

Ich würde mir eine addNode(BinaryTreeNode p) Methode schreiben und eine buildTree(int hoehe)
Bei einem balancierten Baum sind ja die benötigten Knoten für jede höhe bekannt und dann führst du z.B. mit einer while Schleife sooft addNode(BinaryTreeNode p) auf bis du einen kompletten Baum hast.

 

[derfreak]

Wo ist der balanciert ? (oder überseh ich grad was)

 

[PaddyG]

@-Razzer-: Der eigentliche Witz liegt ja im Akkumulator der Schleife, denn irgendwie musst du ja iterativ durch eine rekursive Baumstruktur kommen.

Vorschlag:

public static void generateTree() {

	BinaryTreeNode root = new BinaryTreeNode("root");
	int n = 2;

	LinkedList<BinaryTreeNode> listOfNodes = new LinkedList<BinaryTreeNode>();
	listOfNodes.add(root);

	for (int i = 1; i <= n; i++) {

	        LinkedList<BinaryTreeNode> tempList = 
                         (LinkedList<BinaryTreeNode>) listOfNodes.clone();

		for (BinaryTreeNode node : tempList) {

			// delete root element from list
			listOfNodes.remove(node);

			// create left/right
			BinaryTreeNode left = new BinaryTreeNode("left" + i);
			BinaryTreeNode right = new BinaryTreeNode("right" + i);

			// set left/right to root node
			node.setLeft(left);
			node.setRight(right);

			// add left/right to list
                        listOfNodes.add(left);
                        listOfNodes.add(right);

			}
		}

		printTree(root);
	}

printTree() dient natürlich nur der Ausgabe, printTree() für n=3:

node: root
child: left1
child: right1

node: left1
child: left2
child: right2

node: left2
child: left3
child: right3

node: right2
child: left3
child: right3

node: right1
child: left2
child: right2

node: left2
child: left3
child: right3

node: right2
child: left3
child: right3

Gruß

 

[The Stormrider]

Solang der Baum leer ist, dürfte das mit PaddyGs Algorithmus möglich sein, aber sobald der Baum sortiert werden soll wird das iterativ sehr schwer neue Knoten an der richtigen Stelle hinzuzufügen. Und was bringt mir ein unsortierter Binärbaum? Dann kann ich auch ein Array nehmen

@PaddyG, letzte Ausgabe: wieso ist right3 child von 4 verschiedenen nodes?

 

[PaddyG]

Weil right3 (ebenso wie right2 oder left3) keine eindeutige ID für diesen knoten ist, sondern nur:

BinaryTreeNode left = new BinaryTreeNode("left" + i);

also nur ob links / rechts sowie die aktuelle Ebene als String beeinhaltet. Daher kommen dann gleiche Bezeichnungen für unterschiedlich Knoten zustande.

Und da auf der untersten Ebene insg. 8 Childknoten vorhanden sind, hat man eben 4 x right3 und 4x left3.
Abhilfe schaffen eindeutige Strings als Value

Steht ja nirgendswo geschrieben (je nach konkretem Anwendungsfall, ein BinBaum dient oftmals mehr als nur dem Zahlen sortieren), dass der gleiche Wert nicht in mehreren Knoten stehen darf.

Im übrigen ist tempList leider zwingend nötig, da man nicht dieselbe Liste manipulieren darf, welche gerade von der foreach Schleife durchlaufen wird. Daher auch listOfNodes.clone();.

Gruß
PaddyG