Baum to Array

[bernd1983]

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]

array[i] = x;

 

[Bernd1983]

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

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

 

[mikachu]

hm, vielleicht

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

 

[Bernd1983]

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]

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]

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

 

[mikachu]

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]

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]

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]

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]

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]

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]

habs ausgecodet

funktioniert leider nicht bekomme nur immer 0 zurück

trotzdem thx

bernd

 

[Bernd1983]

entschuldige mein Fehler

funktioniert ausgezeichnet - hab falsch abgetippt

thx @leroy

 

[Bernd1983]

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]

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]

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