# Baum to Array



## bernd1983 (28. Mrz 2006)

Hallo ich möchte einen aufsteigend sortiertem Binärbaum in ein Array konvertieren.

Also mit einer rekursiven Hilfsmethode count bekomme ich die Arraylänge. 
Nur ist mir nicht klar wie ich knoten x im Array an der iten Stelle einfüge.

Vielleicht hat jemand eine idee?

thx

mfg  

bernhd


----------



## byte (28. Mrz 2006)

```
array[i] = x;
```


----------



## Bernd1983 (28. Mrz 2006)

ja das ist mir schon klar a_=x. :lol: 

nur wie sieht die Methode aus die mir x zurückliefert???_


----------



## mikachu (28. Mrz 2006)

hm, vielleicht

```
public Object getX( int i )
{
    return array[i];
}
```


----------



## Bernd1983 (28. Mrz 2006)

also ich glaube ich hab das viel. schlecht erklärt:

ich benötige die methode die in einem aufsteigend sortiertem Binärbaum, immer nur einen Knoten zürückgibt.

ich kenne ja die inorder, aber diese gibt ja den ganzen baum zurück und damit unbrauchbar um in array_ einzufügen._


----------



## Bernd1983 (28. Mrz 2006)

```
int [] reverseArrayOf(Tree t){
		
		int length=t.count();
		
		int [] a=new int[length];
		i++;
                                        for(int i=0;i<.a.length;i++)
			
			a[i]=t.gesuchtemethode;
		
		return a;
		
}

int count(){
		
		return counter(root);
	}

	int counter(Node p){
		
		 
		if(p!=null){
			count++;
		}
		if(p.left==null&&p.right==null){
			return count;
			
		}
		if(p.left!=null){
		  count=counter(p.left);
			
		}if(p.right!=null){
			
		  count=counter(p.right);
			
		}
	return count;
		
	}
```

int gesuchteMethode(){ //fehlt mir}

_//Edit ksg9|sebastian - Code-Tags eingefügt_


----------



## André Uhres (28. Mrz 2006)

http://de.wikibooks.org/wiki/Java_Standard:_Muster_Iterator


----------



## mikachu (29. Mrz 2006)

```
int [] reverseArrayOf(Tree t)
{

    int length=t.count();

    int [] a=new int[length];
    i++;
    for( int i = 0; i < a.length; i ++ )
        a[i]=t.gesuchtemethode;
    return a;
}

int count()
{
    return counter(root);
}

int counter(Node p)
{
    if(p!=null)
    {
        count++;
    }

    if( p.left == null && p.right == null )
    {
        return count;
    }

    if(p.left != null )
    {
        count = counter( p.left );
    }

    if( p.right != null )
    {
        count = counter( p.right );
    }

    return count;
}


int gesuchteMethode()
{
    //fehlt mir
}
```
...ist lesbarer...


----------



## Bernd1983 (29. Mrz 2006)

hallo also mit diesem link hab ich nichts anfangen könne. weiss nicht was mir das für meinen code helfen soll.

Vielleicht weiss noch jemand was


----------



## byte (29. Mrz 2006)

Bernd1983 hat gesagt.:
			
		

> ich benötige die methode die in einem aufsteigend sortiertem Binärbaum, immer nur einen Knoten zürückgibt.



Poste halt mal den Code des Binärbaums, wir sind ja keine Hellseher.


----------



## André Uhres (29. Mrz 2006)

Bernd1983 hat gesagt.:
			
		

> hallo also mit diesem link hab ich nichts anfangen könne.


Auf der Seite steht alles drin. Die gesuchte Methode heisst _gibElement _
und das Anwendungsschema wird in _gibAus _gezeigt.
Ist etwas kompliziert, aber ne Zaubermethode gibt's dafür wohl nicht.


----------



## Bernd1983 (29. Mrz 2006)

```
class Node{
	
	Node left;
	Node right;
	int val;
	Node(int val){
		this.val=val;
	}
	
}//class Node

class Tree{
	
	Node root;
	int count=0;
	int i=0;
	Tree(){
		root=null;
	}
```


----------



## Leroy42 (30. Mrz 2006)

Meine Antwort von gestern Abend, die im falschen Thread gelandet ist:

```
class Tree { 
   private int val; 
   private Tree left; 
   private Tree right; 
   ... 
   public int[] asArray() { 
      int[] array = new int[count()]; 
      asArray(array, 0); 
      return array; 
   } 
    
   int asArray(int[] array, int index) { 
      if (left) index = left.asArray(array, index); 
      array[index++] = val; 
      if (right) index = right.asArray(array, index); 
      return index; 
   }
```


----------



## Bernd1983 (30. Mrz 2006)

habs ausgecodet

funktioniert leider nicht bekomme nur immer 0 zurück

trotzdem thx

bernd


----------



## Bernd1983 (30. Mrz 2006)

entschuldige mein Fehler

funktioniert ausgezeichnet - hab falsch abgetippt 

thx @leroy


----------



## Bernd1983 (30. Mrz 2006)

jetzt versteh ich den algo. aber wie kommt man auf sowas??

wie muss man da denken, damit man rekursive Algos wie der vorherige coden kann?????


----------



## Leroy42 (30. Mrz 2006)

Noch eine Anmerkung:
Deine count()-Methode benötigt eine Instanzvariable count, die ansonsten
nicht benötigt wird, aber auch nicht _Thread-safe_ ist. Das heißt, wenn
zwei Threads _parallel_ diese Methode aufrufen, behindern sie sich
gegenseitig.

Auch wenn du im Moment und später keine Threads benötigst, ist es doch
besser, die count-Methode _unabhängig_ zu machen. Beispiel:


```
class Tree { 
   private int val; 
   private Tree left; 
   private Tree right; 
   ... 
   public int count() {
      int countL = left==null ? 0 : left.count();
      int countR = right==null ? 0 : right.count();
      return countL + countR + 1:
   }
}
```


----------



## Leroy42 (30. Mrz 2006)

Bernd1983 hat gesagt.:
			
		

> Wie muss man da denken, damit man rekursive Algos wie der vorherige coden kann?????



 :shock: Rekursiv denken?  :shock: 

Im Ernst: Wie bei vielem Anderen, ist es einfach nur Übung.

Es hilft auch, ein Faible für _ästhetische Programmierung_ zu haben


----------

