Binärbaum aus Infix- und Präfixordnung erstellen

[metallica787]

Hallo,
für ein Übungsblatt soll ich eine Funktion

BinTree mk_tree(int[] prefix, int[] infix)

schreiben, welche aus der Präfixdarstellung prefix und der Infixdarstellung infix den dazugehörigen Binärbaum konstruiert. Präfix- und Infixdarstellung sollen dabei über int-arrays übergeben werden.

Dazu ist folgende Klasse gegeben, die einen Binärbaum beschreibt:

public class BinTree{
	private Object value;
	private BinTree leftson, rightson;
	
	public BinTree(Object v, BinTree l, BinTree r){
		value = v;
		leftson = l;
		rightson = r;
	}
	
	public Object val(){
		return value;
	}
	
	public BinTree lson(){
		return leftson;
	}
	
	public BinTree rson(){
		return rightson;
	}
	
	public void setVal(Object v){
		value = v;
	}
	
	public void setLson(BinTree l){
		leftson = l;
	}
	
	public void setRson(BinTree r){
		rightson = r;
	}
	
	public boolean isleaf(){
		return leftson == null && rightson == null;
	}
	
	public BinTree leftmost(){
		BinTree p = this;
		BinTree q;
		while ((q = p.lson()) != null)
			p = q;
		return p;
	}
	
	public void addLson(Object v){
		setLson(new BinTree(v, null, null));
	}
	
	public void addRson(Object v){
		setRson(new BinTree(v, null, null));
	}
}

Ich weiss nun absolut nicht wie ich hier vorgehen sollte.
Falls jemand eine Lösung findet, wäre ich überaus glücklich.

 

[SlaterB]

zunächst musst du klären, ob du selber das Problem verstehst,
etwas was du nicht zumindest theoretisch auf dem Papier durchrechnen kannst, kannst du kaum einem PC erklären

Beispiel-Baum-Beschreibung:
Präfix: a b c
Infix: b a c
kannst du daraus den einen möglichen Baum bestimmen oder hälst du mehrere für möglich?
wie sieht es mit längeren Beispielen aus, weißt du immer, welcher Baum es ist

Präfix: g b d e f c a
Infix: d b e f g a c

 

[metallica787]

Ich denke das kann ich.
Folgender Baum sollte dabei entstehen:

 

[SlaterB]

tja, jetzt müßte man nur die Gedanken dazu sortieren können

also mal ein Tipp: am Präfix erkennt man, dass g die Wurzel ist,
am Infix erkennt man danach, dass d b e f den linken Teilbaum bilden und zwar mit
Infix d b e f + Präfix b d e f (aus Haupt-Präfix alles andere streichen)

nun hast du eine vollständige Teilinformation, mit der du auf gleiche Weise von vorne anfangen kannst:
wie sieht der Baum zu Infix d b e f + Präfix b d e f aus

Rekursion ist dazu ein Stichwort, dieselbe Aufgabe nochmal erledigen

 

[metallica787]

Vielen Dank, du hast echt den Stein zum Rollen gebracht
Dass ich Rekursion verwenden musste, war mir fast klar. Nur habe ich nicht daran gedacht, die Arrays zu splitten.

So sieht meine Funktion nun aus:

public static BinTree mk_tree(int[] prefix, int[] infix){
		BinTree p;
		if (prefix.length == 0 && infix.length == 0)
			p = null;
		else{
			p = new BinTree(prefix[0], null, null);
			int dim_inf_left = 0;
			int dim_inf_right = 0;
			int dim_pre_left = 0;
			int dim_pre_right = 0;
			int[] inf_left, inf_right, pre_left, pre_right;
		
			for (int i=0; i<infix.length; i++)
				if (infix[i] == prefix[0]){
					dim_inf_left = i;
					dim_inf_right = infix.length - i - 1;
				}
		
			dim_pre_left = prefix.length - dim_inf_right - 1;
			dim_pre_right = prefix.length - dim_inf_left - 1;
			inf_left = new int[dim_inf_left];
			inf_right = new int[dim_inf_right];
			pre_left = new int[dim_pre_left];
			pre_right = new int[dim_pre_right];
			
			for (int i=0; i<infix.length; i++){
				if (infix[i] != prefix[0])
					inf_left[i] = infix[i];
				else
					break;
			}
			
			for (int i=dim_inf_left+1; i<infix.length; i++)
				inf_right[i-dim_inf_left-1] = infix[i];
			
			for (int i=1; i<prefix.length-dim_inf_right; i++)
				pre_left[i-1] = prefix[i];
			
			for (int i=dim_pre_left+1; i<prefix.length; i++)
				pre_right[i-dim_pre_left-1] = prefix[i];
			
			p.setLson(mk_tree(pre_left, inf_left));
			p.setRson(mk_tree(pre_right, inf_right));
		
		}
		return p;
	}

Habe es mit mehreren Bäumen getestet und es kommt immer das richtige Ergebnis dabei heraus.
Nur frage ich mich nun, ob man den Code nicht noch ein wenig vereinfachen kann.
Dachte da speziell an das Splitten der Arrays, denn meine Lösung scheint mir recht komplex zu sein.

 

[SlaterB]

bisschen besser gehts immer noch, aber das ist schon ganz ordentlich

> dim_pre_left = prefix.length - dim_inf_right - 1;

dim_pre_left ist doch genau gleich dim_inf_left?
generell würde ich auf alle 4 Längenangaben verzichten, verwende immer array.length, dann ist auch gleich die Bedeutung klar,
nur um das Wurzelelement im Prefix-Array zu finden, brauchst du eine int-Variable,
wenn doch Längen als int, dann reichen zwei, denn prefix + infix sind immer gleich lang,

die 4 for-Schleifen am Ende kann man zu einer for-Schleife zusammenlegen,
darin dann gleichzeitig aus beiden Arrays in die 4 neuen kopieren, mit einigen if/else + Indexberechnungen,
ob das schöner ist, ist aber Ansichtssache,

viel mehr als Variablendeklarationen, Wurzelelement-Suche + 4x for hast du aber kaum, das ist jetzt schon ok