Bäume

@vr: War das ein Scherzbeitrag?

LOL! schrieb:

@vr: War das ein Scherzbeitrag?

Oh, hab da in der Tat was vergessen.

Nehmen wir mal an, ich will einen Term in einem binaeren Baum speichern. Dann
hab ich z. B. sowas:

2 * 3 + 4

Daraus erzeugen wir die Postfix-Schreibweise:

2 3 * 4 +

Jetzt gehen wir den Ausdruck durch und kommen zur 2. Wir erstellen einen
Knoten mit 2 und legen diesen auf den Stack. Wir gehen weiter und kommen zur
3, erstellen einen Knoten und legen diesen auf den Stack. Dann kommen wir
zur Operation *, nehmen den ersten Knoten vom Stack, das ist unser rechter
Nachbar des neuen Knotens. Wir nehmen dann die 2 vom Stack und das ist dann
unser linker Nachbar.

Diesen Knoten legen wir nun wieder auf den Stack und lesen die 4. Erstellen
einen Knoten mit der 4, packen diesen auf den Stack und lesen weiter. Wir lesen
+ und gehen genauso vor, wie mit dem *.

Damit ist unser Baum dann aufgebaut. Er sieht dann folgendermassen aus:

So meinte ich das. Ja meine erste Erklaerung war schei**.

mfg
v R

danke,
vielmals

hoffe ich brings jetzt zusammen.

weiß nur noch nicht ob wirs mit einem Stack aufbauen sollen.

aber vorerst hab ich noch meine probleme mit den compilerfehlern.

Der Baum soll nur Name und Telnummer enthalten.

Obwohl ich eine Klasse erstellt hab:

class Knoten		
{
	char name[50];
	int number;

	class Knoten *pr;
	class Knoten *pl;
};

und eine neues Element durch

Knoten *decay;
decay = new Knoten;

kommt folgende Compilermeldung:
Der linke Teil von .number muss eine Klasse/Struktur/Union sein

Irgendwie denk ich mir, dass ich grundlegend was falsch gemacht hab

mfg

sorry,

wollte

class Knoten *decay

schreiben

ZuK

Mann kann das zwar aus deinem Beispiel nicht sicher erkennen aber wahrscheinlich machst du sowas

Knoten *decay;
decay = new Knoten; 
decay.number = 7; // falsch
decay->number = 7; // richtig
(*decay).number = 7; // richtig

holh schrieb:

sorry,

wollte
class Knoten *decay
schreiben

class ist nicht erforderlich
Kurt

wow!

danke,
ich dachte der Punkt und der Pfeil seien dasselbe?
Wo ist da genau der Unterschied?

Und warum brauch ich class nicht hinzuschreiben?

Danke!!

CStoll

"x.irgendwas" ist für Objekte der Klasse/Strukt, "x->irgendwas" ist für Pointer (ist eine Abkürzung für (*x).irgendwas, weil die Kombination aus Dereferenzieren und Elementzugriff doch recht häufig ist)

finix

Ich glaube der OP sucht eher einen balanced (search) tree, keinen Syntax-Tree.

Einfach mal google anwerfen; weitere beliebte Stichworte "AVL", "Red-Black", "BB Alpha", ...

Sorry, komm leider immer noch nicht zurecht.

Wenn ich z.B. schreibe:

newnode(now->pr, decay);

meint der Compiler:

"pr" : Kein Zugriff auf provate Element, dessen Deklaration in der Klasse "Knoten" erfolgte

Was heißt das wieder?!!

Ich halts im Kopf nicht aus

ZuK

wenn deine Klasse Knoten noch immer so aussieht

class Knoten       
{
// public:  // wenn du den kommentar entfernst kann jeder auf alles zugreifen
    char name[50];
    int number;

    class Knoten *pr;
    class Knoten *pl;
};

Dann kann nur ein Knoten auf die membervariablen zugerifen da bei einer Klasse private der default ist. Wenn du aber wirklich public access willst dann nimm lieber eine struct.
Kurt

uh,

und was genau ist der Unterschied zwischen Klasse und Struktur bzw. warum sollte ich bei publiczugriff eine Struct verwenden?

Danke für die Hilfe

ZuK

Bei struct ist der default access public. Sonst gibts keinen Unterschied;
Kurt

So, nachdem immer noch nichts geht poste ich hier einfach mal den code(werden sicher einige Fehler enthalten sein):

# include <iostream>

# include "midwrt.h"

using namespace std;

class Knoten		//Klasse erstellen
{
public:

	char name[50];
	int number;

	class Knoten *pr;
	class Knoten *pl;
};

//////////PROTOTYPEN//////////
void print (Knoten);
Knoten input (Knoten);

///GLOBALE Variablen///
class Knoten *root;

int main()
{

root = new Knoten;
root = NULL;

char name[50];
int number;

class Knoten *now;
now = new Knoten;

class Knoten *decay;
decay = new Knoten;

now = root;

	for(;strcmp("exit", name)!=0;)
	{
		//Einlesen der Daten
		cout << "Name: " << flush << endl;
		cin >> name;
		cout << "Telefonnummer: " << flush << endl << endl;
		cin >> number;

		decay->name = name;
		decay->number = number;

		input(now, decay);	//Schreibvorgang in tree

	}

/////////////////////////////////////////////////////////////

return 0;	//Rückgabewert ans Betriebssystem

}

void input(class Knoten now, class Knoten decay)
{

	now = root;

	do
	{
	if(root == NULL)
		root = decay;

	else if (strcmpi(now->name, decay->name)<0)
		now = now->pr;

	else if (strcmpi(now->name, decay->name)>0)
		now = now->pl;

	}while (now != NULL);

	decay->pl = NULL;
	decay->pr = NULL;

	if(now = NULL)
		now = decay;

	else
		newnode(now, decay);

}

void newnode(class Knoten now, class Knoten decay)
{
	if(decay->name <= now->name)
	{
		if(now->pl == NULL)
			now->pl = decay;

		else
			newnode(now->pl, decay);
	}

	if(decay->name > now.name)
	{
		if(now->pr == NULL)
			now->pr = decay;

		else
			newnode(now->pr, decay);
	}
}

Hoffe ihr könnt was damit anfangen

Vielen Dank für eure Hilfe!
Ihr rettet mir meine Note

ZuK

Ein paar tips.
Prototypen und implementation sollten umbedingt zusammenpassen. Sonst verwirrst du den compiler.
char arrays kannst du nicht einfach mit = zuweisen ( check out strcpy() oder verwende std::string )
dass man char arrays nicht einfach mit == vergleichen kann dürftest du schon bemerkt haben. Der Vergleich auf > oder < funktioniert aber so auch nicht ( strcmp() < 0 )
Kurt

ich hornochse!

anfänglich hatte ich damit begonnen nur eine zahl in den baum zu schreiben.

nachträglich machte ich ein char array dazu.
da hab ich nicht mehr mitgedacht obwohl jener Smilie passender wäre:

^^

danke vielmals für die triviale Hilfe ^^

mfg

root = new Knoten;
root = NULL;

das ist auch nicht soo sinvoll

ähhhhh, da hast wohl recht...

schön langsam wirds schwierig mich noch glaubhaft hinauszureden :p

ähh, weiß jemand wo das Problem liegt, wenn die cin anweisung nichts mehr reinliest trotz flush??

for(;;)
	{

		decay = new Knoten;

		//Einlesen der Daten
		cout << endl << endl << "Name: " << flush;
		cin >> name;

		if(strcmpi(name, "exit") == 0)
			break;

		cout << "Telefonnummer: " << flush;
		cin >> number;

		strcpy(decay->name, name);
		decay->number = number;
		decay->pl = NULL;
		decay->pr = NULL;

		now = root;

		if (now == NULL)
			root = decay;

		else
			*now = newnode(*now, *decay);

	}

ZuK

ähh, weiß jemand wo das Problem liegt, wenn die cin anweisung nichts mehr reinliest trotz flush??

Wenn cin einmal einen fehler hat hilft nur mehr cin.clear().
flush hilft bei cin überhaupt nichts.
Kurt

EDIT: zeig mal wo du Probleme hast kann in dem geposteten code nichts erkennen.
BTW cin und cout sind synchronisiert

cout << endl << endl << "Name: " << flush;
        cin >> name;

das flush ist unnütig.

hab das Problem, dass sich beim 2. mal einlesen der Telefonnummer sich die Nummer einfach nicht ändert.
Denk ich hab nichts grob falsch...

Zudem ist es so, dass beim 2. Knoten durch das

decay = new Knoten

der 2. Knoten wieder überschrieben wird.
Ich denke, dass hat irgendwie mit dem UP zu tun(Übergabe)

Hier also nochmal der ganze Code:

# include <iostream>
using namespace std;

//GLOBALE VARIABLEN//
class Knoten *root;

class Knoten		//Klasse erstellen mit öffentlichem Zugriff, da default private ist
{
public:

	char name[50];
	int number;

	class Knoten *pr;
	class Knoten *pl;
};

//////////PROTOTYPEN//////////

Knoten newnode (Knoten, Knoten);

int main()
{

char name[50];
int number=0;

class Knoten *now;
class Knoten *decay;

	for(;;)
	{

		decay = new Knoten;

		//Einlesen der Daten

		cout << endl << endl << "Name: ";
		cin >> name;
		cin.clear();

		if(strcmpi(name, "exit") == 0)
			break;

	        cout << "Telefonnummer: ";
		cin >> number;
                cin.clear();

		strcpy(decay->name, name);
		decay->number = number;
		decay->pl = NULL;
		decay->pr = NULL;

		now = root;

		if (now == NULL)
			root = decay;

		else
			*now = newnode(*now, *decay);

	}

return 0;	//Rückgabewert ans Betriebssystem

}

Knoten newnode(class Knoten now, class Knoten decay)
{

	if(strcmpi(decay.name, now.name)<=0)
		{
			if(now.pl == NULL)
				now.pl = &decay;

			else
				newnode(*now.pl, decay);
		}

	if(strcmpi(decay.name, now.name)>0)
		{
			if(now.pr == NULL)
				now.pr = &decay;

			else
				newnode(*now.pl, decay);
		}

	return now;
	//*root = now;
}