Aus einem Array ein Bäumchen machen

[Jariel]

Ich soll eine Prozedur schreiben, die aus einem gegebenen Array a ein Binärtree macht.

a[0] ist dann die Wurzel, der linke Nachfolger der Wurzel ist a[1], der rechte Nachfolger ist a[2].
a[1] hat dann die Nachfolger a[3] und a[4] , a[2] hat a[5] und a[6] als Nachfolger usw.

Allgemein gilt: Der linke Nachfolger von a ist a[2*i+1] und der rechte Nachfolger von
a ist a[2*i+2]. Ist der Index 2*i+1 (bzw. 2*i+2) außerhalb des Arrays, so gibt es keinen
linken (bzw. rechten) Nachfolger.



Zum Erzeugen des Baums gibts solche Methoden:

/** Erzeugt einen Baum mit einem einzigen Knoten */
	public BinTree(int v) {
		root = new Node(null, v, null);
	}

	/**
	 * Konstruiert einen Baum, aus zwei gegebenen Teilbäumen und einer neuen
	 * Wurzel mit Wert v.
	 */
	public BinTree(BinTree left, int v, BinTree right) {
		root = new Node(left.root, v, right.root);

Ich hab zB. sowas geschrieben, allerdings weiss ich nicht genau wie ich weitermachen muss:

public static BinTree treeOfArray(int[] a) {
	
		int i = 0;
		BinTree left = new BinTree(a[i*2 + 1]);
		BinTree right = new BinTree(a[i*2 + 2]);
		BinTree blub = new BinTree(left ,a[i], right);
		
		
      return blub;
	}

=> Dann hab ich schonmal die ersten 3 Knoten, aber wie kann ich machen dass der gesamte Baum erzeugt wird, ich denk mal da muss eine Schleife rein, nur wie genau darauf komme ich nicht.

 

[Marco13]

Schleife eher weniger - würde auch gehen, aber ... bei einem Baum bietet sich oft was rekursives an. Sowas wie

public static BinTree treeOfArray(int[] a, int index) 
{
    // Hier drin kommt jetzt irgendwo
        ...treeOfArray(a, xxx) ...
    // und
        ...treeOfArray(a, yyy) ...
    // vor
}

 

[Jariel]

Hm ok, Problem ist aber dass mir die Aufgabenstellung explizit vorgibt dass die Methode diese Form haben soll, ich glaub ich darf da keinen zusätzlichen Parameter einbauen:

public static BinTree treeOfArray(int[] a)

 

[Marco13]

OK, ich gebe dir mal den vollständigen Code für diese Methode:

public static BinTree treeOfArray(int[] a)
{
    return treeOfArray(a, 0);
}

Den Code der Methode

private static BinTree treeOfArray(int[] a, int index)

musst du aber selbst schreiben

 

[Jariel]

Hm ich weiss nicht ob du sowas gemeint hast, aber auf was besseres bin ich nicht gekommen:

-

Allerdings kommt eine ArrayIndexOutOfBoundsException
Ich weiss nicht wieso, ich hab mit den if´s versucht innerhalb der Arraylänge zu bleiben.

 

[Marco13]

Bei den Aufrufen

...
BinTree blub = new BinTree(treeOfArray(a, [b]a[i * 2 + 1])[/b], a[ i ], null);
...

übergibst du den Inhalt des Arrays an dieser Position. Du solltest aber die Position (d.h. den Index) übergeben. Und die NullPointerException wirst du auch noch lösen können.

 

[Jariel]

Ok danke das vorgegebene Testprogramm läuft!