Bäume

Hallo!

Muss einen Binärbaum in C++ schreiben.
inkl. Suche und Ordnung(gegen Degeneration)

Könnte mir irgendwer z.B. einen kleinen Beispielcode der einen Baum aufbaut posten?
Oder zumindest irgendeinen Link oder eine Erklärung wie man einen Baum erstellt.

Hab quasi nirgends etwas gefunden, das mir helfen könnte.

Bitte um eure Hilfe!

mfg

Tach,

einen binaeren Baum baust du folgenderweise auf:

1. Knoten erstellen und mit deinen Informationen belegen
2. Den erstellten Knoten auf einen Stack legen
3. Neuen Knoten erstellen. Den auf dem Stack liegenden holen und abhaengig von
vorher definierten Bedingungen entscheiden, ob der neue Knoten der rechte oder
linke Nachbar von dem alten wird
4. Den Knoten auf den Stack zuruecklegen
5. Wiederhole 3 bis 5 so lange, bis dein Baum komplett ist

Hoffe ich hab nix vergessen. Damit solltest du in der Lage sein, deinen Baum
zu erstellen.

mfg
v R

@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.