Preorder Inorder Postoder

[ETlearner]

hallo,
ich will die methoden pre-post-inorder rekursiv auf ein array anwenden.
dabei ist der name des arrays knoten und die wurzel root stets 0 vor dem methodenaufruf.

ich habe die alogrithmen als text vor mir doch ich kann sie nicht praktizieren-.-

als beispiel für inorder:
1. wurzelknoten=0
2. falls aktueller knoten==null(>array.length) : rekursion beenden
3. linkes kind als aktuellen knoten wählen und zu schritt2
4. aktion ausführen, also knoten ausgeben
5. rechtes kind als aktuellen knoten wählen und zu schritt2

hier die implementationen

public class Baum{

private int root=0;
char[]knoten;


public Baum(char[]values){
knoten=values;
}

private int getLeftChild (int i){
	return 2*i+1;}
	
private int getRightChild (int i){
	return 2*i+2;
	}
	
	
	
	void printInorder(){
		if(root < knoten.length){
		
			while (getLeftChild(root)<knoten.length) {root=getLeftChild(root);
			printInorder();}
			
			System.out.println(knoten[root]);
			
			while (getRightChild(root)<knoten.length){root=getRightChild(root);
			printInorder();
			
			}
			}}

			
			
	void printPreorder(){
			if(root < knoten.length){
				
				System.out.println(knoten[root]);
			
					if(getLeftChild(root)<knoten.length) {root=getLeftChild(root);
					printInorder();}
					
					if(getRightChild(root)<knoten.length){root=getRightChild(root);
						printInorder();
						}
						
						
				}}
				
	void printPostorder(){
			if(root < knoten.length){
				if(getLeftChild(root)<knoten.length) {root=getLeftChild(root);
					printInorder();}
					
				if(getRightChild(root)<knoten.length){root=getRightChild(root);
						printInorder();
						}
						
				System.out.println(knoten[root]);
				}}
			
				
				
	

			
			}

und hier ist die testklasse:

public class TestBaum{

public static void main (String[]args){

char [] values= new char[3];
values[0]='a';
values[1]='b';
values[2]='c';

Baum A= new Baum(values);


A.printInorder();
System.out.println("\n");
A.printPreorder();
System.out.println("\n");
A.printPostorder();
}
}

ich weiß, dass die aufgabe für die meisten in dem forum trivial ist und sie die lösung sofort sehen...
ich habe ca 4 stunden nachgedacht und rumprobiert doch iwie will keine methode klappen...

würde mich sehr auf tipps freuen

mfg

 

[knucki]

Hab es noch nicht kompiliert, aber Rekursion sollte mit Methodenparametern realisiert werden.

Mir fehlt noch der Überblick, welchen Wert "root" zu welcher Zeit bei dir annimmt ^^

 

[ETlearner]

was meinst du mit edit:nix?

 

[ETlearner]

ich habe es auch versucht mit einem 3 ele,emtigen array auf dem blatt zu simulieren und finde auch heraus warum z.b 2 mal b ausgegeben wird...
aber wie ich die methode ändern könnte, sodass es funktionier... darauf komme ich seit 4 stunden nicht

 

[knucki]

Welche Ergebnisse werden denn erwartet?

Mit meinem Schnelltest erhalte ich für
InOrder = b a c
PreOrder = a b c
PostOrder = b c a

 

[ETlearner]

da ist alles richtig

 

[knucki]

public class Baum {

  private static int getLeftChild(final int i) {
    return 2 * i + 1;
  }

  private static int getRightChild(final int i) {
    return 2 * i + 2;
  }

  char[] knoten;

  public Baum(final char[] values) {
    knoten = values;
  }

  public void printInOrder() {
    printInOrder(0);
  }

  public void printPostOrder() {
    printPostOrder(0);
  }

  public void printPreOrder() {
    printPreOrder(0);
  }

  private void printInOrder(final int node) {
    if (node == knoten.length) {
      return;
    }

    if (getLeftChild(node) < knoten.length) {
      printInOrder(getLeftChild(node));
    }

    System.out.println(knoten[node]);

    if (getRightChild(node) < knoten.length) {
      printInOrder(getRightChild(node));
    }
  }

  private void printPostOrder(final int node) {
    if (node >= knoten.length) {
      return;
    }
    if (getLeftChild(node) < knoten.length) {
      printPostOrder(getLeftChild(node));
    }

    if (getRightChild(node) < knoten.length) {
      printPostOrder(getRightChild(node));
    }

    System.out.println(knoten[node]);
  }

  private void printPreOrder(final int node) {
    if (node >= knoten.length) {
      return;
    }

    System.out.println(knoten[node]);

    if (getLeftChild(node) < knoten.length) {
      printPreOrder(getLeftChild(node));
    }

    if (getRightChild(node) < knoten.length) {
      printPreOrder(getRightChild(node));
    }
  }
}

Vielleicht solltest du bei deiner Implementation darauf achten, welche Methoden du wann aufrufst. In Post-/PreOrder hast du rekursiv InOrder z.B. aufgerufen. Desweiteren wurde root nicht reinitialisiert, nach der InOrder-Ausgabe!

 

[ETlearner]

wow so schnell gelöst oO
muss jetzt 1 stunde daran sitzen um es überhaupt zu verstehen
danke sehr

 

[knucki]

Aber gucks dir an und verstehs auch wirklich...

 

[ETlearner]

das mache ich auf jeden fall
die klausur rückt ja auch immer näher
danke nochmals