Pfadlänge eines Baumes berechnen

Neue Frage »

Auf diesen Beitrag antworten »
Matze84 Pfadlänge eines Baumes berechnen

Also ich habe folgenden Baum gegeben.



Dieser Baum sollte erst erstellt werden. (mit Hilfe eine verketten Liste
Dann traversiert werden.

So weit so chic.

Jetzt soll ich Höhe, Knotenanzahl, maximale Pfadlänge, Pfadlänge und Anzahl Blätter bestimmen.

Ich habe alles fertig außer die Pfadlänge.

Dazu weiß ich, dass Die Pfadlänge PL die Summe der Ebenen aller Knoten ist.

Auf dem Papier würde ich rechnen:

1*0+2*1+3*2+4*3+4*5+4*6+5*7+4*8+2*9+2*10+2*11 ....... +1*17+1*18 rechnen.
Ergebnis 312!

Jetzt soll ich das aber programmieren.
Ich bräuchte da mal prinzipiell einen Denkanstoß, wie ich da ran komme...

Wenn ihr noch mehr infos braucht, evtl wie ich die andern Sachen gelöst habe, dann sagt bescheid und ich werde das hier posten.

Danke schon mal
 
Auf diesen Beitrag antworten »
eulerscheZahl

Du könntest zum Beispiel die Sprache angeben.
Ich habe C genommen, weil ich dann einen alten Beitrag wiederverwenden kann.
In C# ginge es mit einem ref an Stelle des Zeigers.
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:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
#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);
}

void pfadlaenge(struct Knoten* kn, int tiefe, int* summe)
{
	if(kn == NULL) return;
	*summe += tiefe;
	pfadlaenge(kn->links, tiefe+1, summe);
	pfadlaenge(kn->rechts, tiefe+1, summe);
}

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);
	int laenge = 0;
	pfadlaenge(wurzel, 0, &laenge);
	printf("Pfadlaenge = %d", laenge);
	getchar();
}
Auf diesen Beitrag antworten »
Matze84

ok guck ich mir mal an und geh das mal durch... melde mich ggf dann nochmal.
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »