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

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

  • F

    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

    0
  • D

    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!

    0
  • F

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

    0
  • D

    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?

    0
  • F

    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

    0
  • D

    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.

    0
  • F

    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

    0
  • D

    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.

    0
  • F

    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.

    0
  • C

    //zu früh absenden geklickt

    0
  • C

    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 😕

    0
  • F

    also eigentlich ist mir die funktionsweise der rekursion schon klar, ich habe auch schon einige funktionen rekursiv geschrieben, z.b. die ausgabe einer linearen liste.

    ich glaube der punkt an dem ich mich im moment aufhänge, ist dieses zurückgehen.

    ich bin am punkt d angekommen. nun ist d->left==null also abbruch, er springt weiter zu printf und danach macht er d->right, was auch null ist-> also abbruch.

    nun ist mir irgendwie nicht ganz klar, warum er wieder zu b zurückkehrt und dann direkt zu b->rigt springt 😕

    irgendwie doof zu erklären. rekursion ist schon irgendwie merkwürdig, mir ist schon irgendwo klar was da passiert, aber am ende ergibt es doch keinen sinn 😛

    €: in den rekursionen, die ich bereits geschrieben habe, gab es immer ein return, vielleicht habe ich mich auch daran aufgehängt.
    ich glaube ich muss einfach verstehen, wieso er wieder einen wert zurückspringt.

    so ich glaube irgendwie hab ichs jetzt, bei nem baum mit zwei kindern ohne blätter kann ich den ablauf nachvollziehen, wenn er größer wird bleibt es ja das gleiche, nur das die rekursion tiefer wird.
    sehr verwirren das ganze, aber interessant.

    lg

    0
  • C

    curry-king schrieb:

    Das Konzept der Rekursion ist Dir klar?

    FedX schrieb:

    also eigentlich ist mir die funktionsweise der rekursion schon klar...

    FedX schrieb:

    nun ist mir irgendwie nicht ganz klar, warum er wieder zu b zurückkehrt und dann direkt zu b->rigt springt

    😃

    Mach Dir klar, das eine Methode nach der letzten "}"-Klammer auch ohne "return" ZU IHREM AUFRUFER zurückkehrt!

    Wenn also der Methodenaufruf inorder(b->left) seine Arbeit getan hat und (in den Methodenaufruf inorder(a->left) ) "zurückkehrt", wird als nächstes printf(b) aufgerufen und darauf folgend inorder(b->right).

    Besser?

    0
  • F

    ja danke 🙂
    jetzt isses mir klar.
    ich hatte da wohl irgendwo eine denkblockade 😃
    programmieren kann ganz schön konfus sein :p

    0
  • F

    will keinen neuen thread aufmachen.
    bin nun beim hashing angelangt.
    ich soll eine hashtabelle erstellen wenn eine kollision auftritt wird in baumform hinter dem gleichen key gespeichert.

    nun habe ich ein problem ich habe ein struct node und eine hashtabelle:

    hashtree[10]={0};

    wenn ich hier nun einen wert reinschreiben will und zwar so:

    hashtree[a]=(node*)malloc(sizeof(node));

    (hashtree[a]->data)=eingabe;

    a ist der zuvor errechnete key für das eingegebene wort char eingabe[30]

    nun bekomm ich den fehler, dass der ausdruck ein änderbarer value sein muss, der fehler trirr vor (hashtree[a]->data)=eingabe;
    was mache ich falsch ??

    €: bewirkt {0}, dass das gesammte array mit 0 gefüllt wird??

    lg

    0
  • B

    Schau mal in deinem Buch unter dem kapitel Array nach was Array[]={0} macht.
    Du solltest dir angwöhnen malloc nicht zu casten.
    Kannst du nicht den original Fehler posten? Aus deiner übersetztung werde ich nicht ganz schlau...

    0
  • T

    Du solltest dir angwöhnen malloc nicht zu casten.

    .. nicht zu benutzen sollte es wohl heissen ..

    🙄 ehm.. sorry.. dachte ich sei im C++ forum.. ich schussel..

    0
  • F

    er sagt mir, dass der linke wert kein L-wert sei, aber eigentlich muss ich hashtree[a]->value doch einen wert zuweisen könnten oder nicht?

    was meinst du mit casten ? die typumwandlung auf(node*)?

    falls es von ineresse ist, hier der bisherige code:

    #include"programmskizze.h"

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

	return auswahl;

}

typedef struct Node_ 
{
    charArray data;             /* data stored in node */
    struct Node_ *left;         /* left child */
    struct Node_ *right;        /* right child */
} node;

void getline(char *feld,int laenge)
{
int z=0;
int ch=0;
laenge=laenge-1;

fflush(stdin);

for(z=0;(z<laenge)&&((ch=getchar())!=EOF)&&(ch != '\n');z++)
{
feld[z]=(char) ch;
}
feld[z]='\0';

if(z==laenge)
{
printf("Ihr eingegebenes Wort ist zu lang\n");
printf("Uebernommenes Wort: %s\n",feld);
}
}

int asciiumwandlung(int a)
{int i;
 int z=0;
		for(i=65;i<=90;i++)//für großbuchstaben
		{
			if(a==i)
				return z;
			else
			z++;
		}

		for(i=97;i<=122;i++)
		{
			if(a==i)
				return z;
			else
			z++;
		}
printf("konnte dem buchstaben %c keinen wert zuweisen",a);
}

int hashkey(char*eingabe,int behälter)
{int i;

	i=((asciiumwandlung(eingabe[0])+asciiumwandlung(eingabe[1])+asciiumwandlung(eingabe[2])+asciiumwandlung(eingabe[3]))%behälter);
	return i;
}

main()
{
	int auswahl;
	int a;
	charArray eingabe;//char array definiert ein array mit ARRAY_ELEMTS elementen

	node *hashtree[10] = {NULL};

	auswahl=menu_ausgabe();

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

		printf("bitte geben sie ihr wort ein(nicht mehr als 30buchstaben):\n");

			getline(eingabe,ARRAY_ELEMENTS);

			a=hashkey(eingabe,10);	//hashkey wird ermittellt

			hashtree[a]=(node*)malloc(sizeof(node));

			(hashtree[a]->data)=eingabe;

		}
	}

}

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

#define ARRAY_ELEMENTS 30

typedef char charArray[ARRAY_ELEMENTS]; /* type of item to be stored */

    in zeile 103 kommt der fehler mit dem l wert

    lg

    0
  • B

    @theta bleib in deinem Forum, new kann doch jedes kleine kind verwenden... 😉

    Du hast da glaub einige Kapitel übersprungen. Oder du hast Bei den Arrays geschlafen. Es ist noch nie möglich gewesen einen Array mit = an einem Anderen Array zuzuweisen. Versuche es mit strcpy.

    was meinst du mit casten ? die typumwandlung auf(node*)?

    Ja!

    0
  • F

    ach verdammt, ja da war was.

    als ich vorhin mit dem programm angefangen hab hab ich noch dran gedacht, habs dann wohl beim programmieren vergessen.
    danke

    0
Anmelden zum Antworten