# Aus einem Array ein Bäumchen machen



## Jariel (15. Jan 2011)

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:


		Java:In die Zwischenablage kopieren


/** 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:




		Java:In die Zwischenablage kopieren


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 (15. Jan 2011)

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 (15. Jan 2011)

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 (15. Jan 2011)

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 (16. Jan 2011)

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 (16. Jan 2011)

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 (16. Jan 2011)

Ok danke das vorgegebene Testprogramm läuft!


----------

