Baum aus Liste (inorder) aufbauen

14.01.2013, 17:35

xyz123

Baum aus Liste (inorder) aufbauen

Hallo,

ich habe eine Datei, in der Elemente drinstehen, die der Größe nach geordnet sind. Nun möchte ich den Baum so aufbauen, dass er ausgeglichen ist.
Meine Frage: Wenn ich rekursiv in der funktion ausgleichen die Parameter pBaum und n (die Anzahl der Elemente) übergebe, wie muss ich dann rekursiv beim linken und rechten Teilbaum das n übergeben? Also immer die Mitte ist schon klar, aber geht nur bei links... wie geht das bei rechts?? Zunge raus

14.01.2013, 19:45

Auf diesen Beitrag antworten »

eulerscheZahl

Ein Element fällt weg, da es im Baum eingefügt wird.
Es bleiben also n-1 Elemente übrig.
links=(n-1)/2 //abgerundet
rechts=n-1 - links

Dadurch sind rechts und links gleich groß (evtl. Abweichung von 1) und ergeben zusammen n-1 Elemente.

Zahlenbeispiel:
n=18
links=(18-1)/2=8
rechts=18-1 - 8=9

14.01.2013, 21:45

Auf diesen Beitrag antworten »

xyz123

danke, aber so ganz funktioniert das nicht. wie würde denn dann folgender Baum aufgebaut werden?
immer Wurzelobjekt einfügen; ausgleichen(linkerTeilbaum.create); ausgleichen(rechterTeilbaum.create); und noch ein bischen aus Datei auslesen und so mal weggelassen - rekursiv.

Bsp: 6 7 8 9 12 18 22 33 40 41 45

15.01.2013, 09:00

Auf diesen Beitrag antworten »

eulerscheZahl

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:

#include <stdio.h>
#include <stdlib.h>

struct Knoten
{
    struct Knoten *rechts;
	struct Knoten *links;
	int wert;
};

struct Knoten* ausgeglichen(int MeinArray[], int start, int n)
{
    int links, rechts;
	struct Knoten* kn;
	if(n==0) return NULL;
    links=(n-1)/2;
	rechts=n-1-links;
	kn=(struct Knoten*)malloc(sizeof(struct Knoten));
	if(kn==NULL) return NULL;  //kein Speicher vorhanden
	kn->wert=MeinArray[start+links];
	kn->links=ausgeglichen(MeinArray,start,links);
	kn->rechts=ausgeglichen(MeinArray,start+links+1,rechts);
	return kn;
}

void PrintTree(struct Knoten*kn, int ordnung)
{
    int i;
    if(kn==NULL) return;
	PrintTree(kn->rechts, ordnung+1);
	for(i=0;i<ordnung;i++) printf("     ");
	printf("%5d\n",kn->wert);
	PrintTree(kn->links, ordnung+1);
}
int main(void)
{
    int MeinArray[]={6, 7, 8, 9, 12, 18, 22, 33, 40, 41, 45 };
	struct Knoten* Wurzel=ausgeglichen(MeinArray,0,sizeof(MeinArray)/sizeof(MeinArray[0]));
	PrintTree(Wurzel,0);
	getchar();
}

Ausgabe:

code:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:	45 41 40 33 22 18 12 9 8 7 6

Neue Frage »

Antworten »

Baum aus Liste (inorder) aufbauen

Verwandte Themen