suche hilfe: rekursives einfügen in einen binärbaum

Binggi

Versuche es Mal so...

treenode*root=malloc(sizeof(treenode));

FedX

an welcher stelle soll ich das ändern?
wenn ich das so in den compiler eintrage, sagt der mir, dass ein typ void nich zur intitialisierung genutzt werden kann, oder sowas in der art.

lg

Binggi

An dieser Stelle

treenode*root=0;

Du musst root auch einen Speicher zuweisen. Aber ich habe mir das Programm nicht genau angeschaut. Versuche es einmal mit deinem Debugger... Dann wirst du auch schnell die Stelle finden an dem das Programm stecken bleibt.
Lg

FedX

also bei visual 2010 kann ich das programm wie es ist ohne probleme compilieren und bekomme keine fehler.

es stürzt einfach nur ohne vorwarnung ab, sobald man den ersten wert einlesen will.

FedX

wenn ich den speicher ganz am anfang allokiere, dann kommt wieder diese fehlermeldung.
wenn ich ihn unter der while schleife allokiere dann kommt zwar keine fehlermeldung mehr, aber er springt auch nicht in meine funktion einfuegen(root,neu).

was mache ich falsch? ist wenigstens der grundgedanke mit dem einfügen richtig?

lg

FedX

so ich hab jetzt mal versucht immer bevor ich etwas in root schreiben will extra in der funktion speicher zu allokieren
wenn ich das am anfang der funktion einmal machen würde, hätte ich ja das problem, dass root nicht mehr null ist un somit nicht mehr klar ist, ob nun schon eine wurzel vorhanden ist oder nicht

#include"baum.h"

typedef struct treenode
{int key;
struct treenode *left,*right;

}treenode;

int menu_ausgabe(void)
{ 
	int auswahl;
	do
	{
	printf("\n menue\n --------------\n 1...Eingabe\n 2...Ausgabe inorder\n 3...ausgabe preorder\n 4...ausgabe postorder\n ");
	scanf("%d", &auswahl);
	}
	while ((auswahl>6) || (auswahl<1));

	return auswahl;

}

treenode* einfuegen(treenode*root,treenode*neu)
{	

	if(root==0)//noch kein knoten vorhanden root zeigt ins nichts
	{	
		root=(treenode*)malloc(sizeof(treenode));
		(root->key)=(neu->key);
		(root->left)=0;
		(root->right)=0;
		printf("neue wurzel %i wurde erstellt\n",root->key);
		return root;
	}
	else//es ist bereits ein knoten vorhanden
	{
			if((neu->key)<(root->key))
			{
				if((root->left)==0)//der linke knoten ist frei
				{
				root=(treenode*)malloc(sizeof(treenode));
				(root->left)=neu;
				(neu->left)=0;
				(neu->right)=0;
				printf("der linke knoten von %i wurde mit %i gefuellt\n",root->key,neu->key);
				}

				else //der linke knoten ist besetzt
				{	
					printf("da linker knoten besetzt ist, wird weiter gegangen");
					einfuegen(root->left,neu);//mach alles nochmal nur mit dem linken teil als wurzel
				}
			}

			if((neu->key)>(root->key))//der einzufügende wert muss an die rechte stelle, da kleiner
			{
				if((root->right)==0)//ist der rechte teil des knotens frei??
				{
				root=(treenode*)malloc(sizeof(treenode));
				(root->right)=neu;
				(neu->right)=0;
				(neu->left)=0;
				printf("der rechte knoten von %i wurde mit %i gefuellt",root->key,neu->key);
				}
				else//der knoten ist nicht fre
				{	
					printf("der rechte knoten ist besetzt, springe zum nachsten\n");
					einfuegen(root->right,neu);

				}
			}
	return root;
	}

}

main()
{
int auswahl;
treenode*neu=0;
treenode*root=0;

char j='j';

while(1)
{
auswahl=menu_ausgabe();

	if(auswahl==1)
	{
		while(j=='j')
		{   

			neu=(treenode*)malloc(sizeof(treenode)); 

			printf("wert:\n");

			fflush(stdin);
			scanf("%i",&neu->key);

			root=einfuegen(root,neu);

			printf("einen weiteren wert einlesen? j/n \n");
			fflush(stdin);
			scanf("%c",&j);
		}
	}

}

}

David_pb

Beim verlinken geht einiges schief:

if((root->left)==0)//der linke knoten ist frei
{
    root=(treenode*)malloc(sizeof(treenode)); // wieso? root gibts doch schon
    (root->left)=neu;
    (neu->left)=0;
    (neu->right)=0;
    printf("der linke knoten von %i wurde mit %i gefuellt\n",root->key,neu->key);
}

Genauso beim zweiten Fall (root->right == 0).

FedX

ach jetzt versteh ich, sobald root irgendwo schon einmal allokiert wurde, muss ich das nicht nocheinmal machen?
und da, wenn ich die wurzel erstelle root allokiert wird kennt der compiler das dann?

jetzt scheint es wirklich zu funktionieren juhu

ich merke gerade, dass das ding keine doppelten werte aufnimmt, da mach ich mich ma schnell ran

lg

David_pb

FedX schrieb:

und da, wenn ich die wurzel erstelle root allokiert wird kennt der compiler das dann?

Der Compiler weiss von nichts. Mit malloc holst du dir den Speicher zu Laufzeit und behältst den solang du ihn nicht explizit wieder freigibst (mit free, das nicht vergessen).

FedX

ok gut.

free brauche ich aber erst dann, wenn ich aus dem baum was löschen will, damit dann nicht irgendwo was rumfliegt, auf das kein pointer mehr zeigt und ich somit nie wieder zugreifen kann,oder?

lg

David_pb

FedX schrieb:

ok gut.

free brauche ich aber erst dann, wenn ich aus dem baum was löschen will, damit dann nicht irgendwo was rumfliegt, auf das kein pointer mehr zeigt und ich somit nie wieder zugreifen kann,oder?

Genau!

FedX

wo werden denn werte gespeichert, die schon vorhanden sind rechts, oder links? gibts da vielleicht eine regel?

David_pb

FedX schrieb:

wo werden denn werte gespeichert, die schon vorhanden sind rechts, oder links? gibts da vielleicht eine regel?

Versteh grad nicht worauf du hinaus willst?

FedX

wenn ich zb als ersten wert ne 5 eingebe, dann ist das ja meine wurzel.
wenn ich jetzt jedoch noch einmal 5 eingebe, weiss das programm im moment nicht was es machen soll, da nur größer oder kleiner als 5 als weg definiert ist, nicht aber ==.
im moment scheint das programm einfach gar nichts zu tun.

oder kommen in so einem diagramm niemals gleiche werte vor?

lg

David_pb

Doch, allerdings ist das in diesem Fall ja belanglos. Weil der Schlüssel ja der selbe ist und allerhöchstens ausgetauscht werden müsste. Wichtiger ist es wenn du mit Schlüsseln noch andere Werte assoziierst, dann müsstest du im Fall root.key == new.key den Wert aktualisieren.

FedX

das versteh ich nun nicht, wie meinst du das mit gleichem schlüssel andere werte assoziieren?
ich fülle meinen baum ja nur mit integern, da ist doch ne 5 einfach ne 5 und nichts anderes.

mit den schlüsseln erinnert mich irgendwie an hashing, da muss ich auch noch nen crashkurs machen.

lg

David_pb

FedX schrieb:

das versteh ich nun nicht, wie meinst du das mit gleichem schlüssel andere werte assoziieren?
ich fülle meinen baum ja nur mit integern, da ist doch ne 5 einfach ne 5 und nichts anderes.

mit den schlüsseln erinnert mich irgendwie an hashing, da muss ich auch noch nen crashkurs machen.

lg

Im Allgemeinen legt man noch weitere Daten im Baum ab die dann anhand des "Schlüssels" in den Baum "einsortiert" werden. Die Schlüssel stehen natürlich irgendwie in Beziehung mit dem Wert.

FedX

ok, jetzt versteh ichs, glaub ich

könnte mir vielleicht jemand folgende rekursive funktion zur inorder traversierung erklären?

void inorder(treenode*root)
{
if(treenode!=0)
   {inorder(treenode->left);
    printf("%i",root->key);
    inorder(treenode->right);
   }
}

ich habe es selbst einfach nicht hinbekommen diese traversierung durchzuführen.
diesen code habe ich gefunden und angepasst und es funktioniert.

nur ist mir die funktionsweise dieser rekursion nicht so ganz klar, denn eigentlich gehe ich ja solange nach links, bis treenode auf null zeigt und dann passiert nichts weiter
aber irgendwie scheint es ja doch weiter zu gehen und auch zu funktionieren.

kann vielleicht jmd einen ablauf anhand eines baumes mit einer wurzel, zwei kindern und 4 blättern erklären??
danke.

curry-king

//zu früh absenden geklickt

curry-king

FedX schrieb:

denn eigentlich gehe ich ja solange nach links, bis treenode auf null zeigt und dann passiert nichts weiter

Das Konzept der Rekursion ist Dir klar? Gut!
Wenn die Funktion inorder am linkesten Knoten angekommen ist, kehrt die Funktion zum Aufrufer zurück, welcher dann seine Arbeit bei printf fortführt und so inorder auf den rechten Teilbaum anwendet.

a
       / \
      b   c
     / \
    d   e

Lauf:
inorder(a->left)
inorder(b->left)
inorder(d->left)
Rückkehr aus inorder(d->left) und printf(d)
inorder(d->right)
Rückkehr aus (d->right) zu b
inorder(b->right)
inorder(e->left)
Rückkehr aus (e->left) und printf(e)
inorder(e->right)
.
.
.

Ist das so klar geworden