C++ Baum

[Gast]

Ich denke volkard meinte das so, oder?

void TreePrintPostorder(node *root, node* z, int* nochAuszugeben) 
{
if(*nochAuszugeben==0) return;
	if (root != z)
	{
		TreePrintPostorder(root->l, z, nochAuszugeben);
		TreePrintPostorder(root->r, z, nochAuszugeben);
		if(*nochAuszugeben==0) return;

		cout <<root->messwerte <<" ";
		--*nochAuszugeben;
	}
}

void TreePrintPostorder(node *root, node* z, int nochAuszugeben) 
{
	TreePrintPostorder(root, z, &nochAuszugeben);
}

Aber eigentlich wollte ich Fragen, warum du einen Zeiger auf nochAuszugeben der Referenz vorziehst?
Hat das einen Grund oder nur 'Zufall'? Denn Referenzen haben (wie ich finde)
eine übersichtlichere Syntax.

[michael_xsx]

Danke für die Anwort.

ich hab das jetzt mal versucht so zu machen, ich versteh nur nicht warum ich eine 2 Funktion brauche die genau gleich heißt?
Naja es git bei mir ein Problem mit int* nochAuszugeben. Wenn ich das im hauptprogramm auf 3 setze geht es nicht leider.

[volkard]

CSpille schrieb:

Aber eigentlich wollte ich Fragen, warum du einen Zeiger auf nochAuszugeben der Referenz vorziehst?
Hat das einen Grund oder nur 'Zufall'? Denn Referenzen haben (wie ich finde)
eine übersichtlichere Syntax.

Weil ich reinschreibe. Ich optimiere für den Aufrufer, nicht für das Werkzeug. Der Aufrufer muß sehen, daß da eine Veränderung der Variablen geplant ist.

Aber ich hab schon dran gedacht, hier aus Faulheit mal schnell eine Referenz zu nehmen. Dann ist mir aber eingefallen, daß michael_xsx drum gebettelt hat, noch ein wenig mit Zeigern üben zu dürfen. Da hab ich's ihm halt besorgt.

[michael_xsx]

//Baum_01
//12.05.2010

#include <conio.h>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

using namespace std;

struct node   //Strucktur Baum
{
	int messwerte;
	int info;
	node *l;
	node *r;
};

typedef node* bstPtr;

void selection(int[], int);
void treeinitialize(node* , node*);
void treeinsert(node* , node*, int, int);
void TreePrintInorder(node*  , node*);
void TreePrintPreorder(node* , node*);
void TreePrintPostorder(node* , node*);
void TreePrint3Postorder(node* , node*, int*);
int treesearch(node* , node*, int);
void durchschnitt(node* , node*,int&); 
void deleteall(node* , node*);

void main()
{
	char auswahl2 = 'J';
	do
	{   
		int messwerte = 0;       //Werte
		int einfuegewerte = 0;   //für die automatischen Werte
		int nCount = 0;          //Mitzähler
		int suche = 0;           //für suche
		int search = 0;          //für suche
		int info = 0;          //wird benötigt zusätzlich zu den Werten
		int durchschnittswert = 0;  //für Berechnung

        //Baum
		node* root = new node;   
		node* z = new node;      

        //Bauminetialisiereung
		treeinitialize(root , z);  

		//Eingabe der Zufallszahlen!
		system("cls");
		cout <<"Anzahl der Zufallszahlen: ";
		cin >> nCount;

        // Eingabe muss positiv sein!
		if (nCount < 0)    
		{
			do
			{
				cout <<endl;
				cout <<"Die Eingabe muss positiv sein!\n\n";
				cout <<"Anzahl der Zufallszahlen: ";
				cin >> nCount;

			}while (nCount < 0);
		}

        // Dynamisches array erstellen
		int* nKeys = new int[nCount];  

        // Zufallszahlen erstellen
		srand(GetTickCount());    

        //Array mit Zufahlszahlen befüllen
		for (int i = 0; i<nCount; i++)  
		{
			nKeys[i] = rand() % (nCount*5);
		}

        // Ausgabe der arry Zahlen
		cout << endl;                     
		cout <<"Zahlen im Array!\n\n";

		for(int j = 0; j < nCount; j++) 
		{
			cout << nKeys[j] <<" ";
		} 

        // Sortierung mit Selection (Aufsteigend)
		selection(nKeys, nCount);   

        //Befüllen des Baumes mit automatisch generierten Zahlen
		for(int k = 0; k < nCount; k++) 
		{

			einfuegewerte = nKeys[k];
			info ++;

			treeinsert(root, z, einfuegewerte, info);

		} 

		//Löschen des nicht mehr nötigen dynamischen Arrays
		delete nKeys;

        //Ausgabe der Daten mit Inorder (Aufsteigend)
		cout << endl;
		cout <<"--------------------\n";
		cout <<"Inorder-Traverse:\n";
		cout <<"--------------------\n";
		TreePrintInorder(root->r, z);      

        //Ausgabe der Daten mit Preorder
		cout << endl;
		cout <<"--------------------\n";
		cout <<"Preorder-Traverse:\n";
		cout <<"--------------------\n";
		TreePrintPreorder(root->r, z);

        //Ausgabe der Daten mit Postorder (Absteigend)
		cout << endl;
		cout <<"--------------------\n";
		cout <<"Postorder-Traverse:\n";
		cout <<"--------------------\n";
		TreePrintPostorder(root->r, z);

 //Ausgabe der Daten mit Postorder (Absteigend)
		cout << endl;
		cout <<"---------------------\n";
		cout <<"Die größten 3 Zahlen:\n";
		cout <<"---------------------\n";
	    TreePrint3Postorder(root, z, 3);

		//Zahl suchen (ob vorhanden oder nicht)
		cout <<"\n\n";
		cout <<"Geben sie den zu suchende Zahl ein: ";
		cin >> suche;

		search = treesearch(root , z, suche);

		if (search == -1)   // wenn nicht gefunden
		{
			cout <<endl;
			cout<< "Nicht gefunden!\n";
		}
		else                // wenn gefunden
		{
			cout <<endl; 
			cout << "Gefunden! " <<endl;
		}

        //Berechnen des Durchschnittswert
		durchschnitt(root->r, z, durchschnittswert);
		cout << endl;
		if (durchschnittswert == 0)   //wenn nichts in der Liste
		{
			cout << endl;
			cout <<"Keine Werte eingegeben!\n";

		}
		else                         //sonnst
		{
			cout <<"Der Druchschnittswert ist: " << durchschnittswert/info << endl;
			durchschnittswert = 0;

		}

        //Baum komplett löschen
		deleteall(root->r,z);
		root->r = z;
		info = 0; 
		cout << endl;
		cout <<"Alle Daten geloescht!\n";

        //Programm noch einmal ausführen?
		cout << endl;
		cout << endl;
		cout <<"Wollen Sie das Programm noch mal ausfuehren? (J/N)\n"; 
		cin >> auswahl2;
		cout << endl;

        //Löschen des dynamischen Speichers
		delete root;
		delete z;

        //Abbruchbedingung
	}while ( auswahl2 == 'j' || auswahl2 == 'J');  

	_getch();
}

// Selection sortierung (Aufsteigend)
void selection(int nKeys[], int nCount)  
{
	int i, j, min, t = 0;

	for(i = 0; i < nCount; i++) 
	{
		min = i;

		for(j = i+1; j < nCount; j++)
			if(nKeys[j] < nKeys[min])
				min = j;

		t = nKeys[min];
		nKeys[min] = nKeys[i];
		nKeys[i] = t;
	}

    // Ausgabe der Sortierten Zahlen
	cout <<"\n\n";                     
	cout <<"Zahlen Sortiert im Array!\n\n";

	for(i = 0; i < nCount; i++) 
	{
		cout << nKeys[i] <<" ";
	} 
	cout << endl;
}

//Bauminetialisiereung
void treeinitialize(node *root , node* z)
{
	z->l = z; 
	z->r = z; 
	z->info = -1;
	z->messwerte = -1;

	root->r = z; 
	root->l = z;
	root->messwerte = 0;
	root->info = 0;
}

//Einfügen der Elemente in den Baum
void treeinsert(node* root, node* z, int messwerte, int info)
{
	node *p, *x;
	p = root; 
	x = root->r;

	while(x != z)
	{
		p = x;
		if(messwerte < x->messwerte)
			x = x->l;
		else
			x = x->r;
	}

	x = new node;
	x->messwerte = messwerte; 
	x->info = info; 
	x->l = z; 
	x->r = z;

	if(messwerte < p->messwerte)
		p->l = x;
	else
		p->r = x;
}

//Ausgabe Inorder (Aufsteigende sortierung , Alphabet)
void TreePrintInorder(node *root , node* z) 
{                                          
	if (root != z)
	{
		TreePrintInorder(root->l, z);
		cout << root->messwerte <<" ";
		TreePrintInorder(root->r, z);
	}
}

// Ausgabe Prorder (WLR)
void TreePrintPreorder(node *root, node* z) 
{
	if (root != z)
	{
		cout <<root->messwerte <<" ";
		TreePrintPreorder(root->l, z);
		TreePrintPreorder(root->r, z);
	}
}

//Ausgabe Postorder (Absteigende Sortierung)
void TreePrintPostorder(node *root, node* z) 
{
	if (root != z)
	{
		TreePrintPostorder(root->l, z);
		TreePrintPostorder(root->r, z);
		cout <<root->messwerte <<" ";
	}
}
//Ausgabe der größten 3 Zahlen
void TreePrintPostorder(node *root, node* z, int* nochAuszugeben)
{
if(*nochAuszugeben==0) return;
    if (root != z)
    {
        TreePrintPostorder(root->l, z, nochAuszugeben);
        TreePrintPostorder(root->r, z, nochAuszugeben);
        cout <<root->messwerte <<" ";
        ++*nochAuszugeben;
    }
}

//Suche im Baum nach einem Wert
int treesearch(node* root, node* z, int suche)
{
	node *x = root->r;
	z->messwerte = suche;

	while(suche != x->messwerte)
	{	
		if(suche < x->messwerte)
			x = x->l;
		else
			x = x->r;
	}
	return x->info;
}

//Berechnung für einen Durchschnittswert
//Zusammenzählen der Werte mit Hilfe der Inorder Ausgabe
void durchschnitt(node *root , node* z, int& durchschnittswert) 
{
	if (root != z)
	{
		durchschnitt(root->l, z,durchschnittswert);
		durchschnittswert += root->messwerte;
		durchschnitt(root->r, z,durchschnittswert);
	}
}

//Löschen des gesammten Baumes
void deleteall(node *root, node *z)
{
	if (root->l != z)
		deleteall(root->l, z); 

	if (root->r != z)
		deleteall(root->r, z);  
}

[volkard]

michael_xsx schrieb:

Danke für die Anwort.

ich hab das jetzt mal versucht so zu machen, ich versteh nur nicht warum ich eine 2 Funktion brauche die genau gleich heißt?
Naja es git bei mir ein Problem mit int* nochAuszugeben. Wenn ich das im hauptprogramm auf 3 setze geht es nicht leider.

Genau.

TreePrint3Postorder(root, z, 3);

geht so nicht. Du mußt Speicher anlegen und dessen Adresse übergeben.

int merker=3;
TreePrint3Postorder(root, z, &merker);

Und genau das macht die zweite Funktion!

Natürlich sind CSpilles Reparaturen angebracht.

[Gast]

michael_xsx schrieb:

ich hab das jetzt mal versucht so zu machen, ich versteh nur nicht warum ich eine 2 Funktion brauche die genau gleich heißt?
Naja es git bei mir ein Problem mit int* nochAuszugeben. Wenn ich das im hauptprogramm auf 3 setze geht es nicht leider.

Die Funktionen brauchen natürlich nicht den gleichen Namen, es bietet sich nur an.

In deinem Code steht noch ein ++ statt -- und eine zusätzliche Bedingung mit
return fehlt.

[michael_xsx]

Danke jetzt geht es!
Das hätte ich selber nicht geschaft, naja da muss ich noch etwas üben in C++.

Der fertige Code vom Programm, falls jemand mal mit Bäumen zu tun hat.

Nochmal großes DANKE!

//Baum_01
//12.05.2010

#include <conio.h>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>

using namespace std;

struct node   //Strucktur Baum
{
	int messwerte;
	int info;
	node *l;
	node *r;
};

void selection(int[], int);
void treeinitialize(node* , node*);
void treeinsert(node* , node*, int, int);
void TreePrintInorder(node*  , node*);
void TreePrintPreorder(node* , node*);
void TreePrintPostorder(node* , node*);
void TreePrint3Postorder(node* , node*, int*);
int treesearch(node* , node*, int);
void durchschnitt(node* , node*,int&); 
void deleteall(node* , node*);

void main()
{
	char auswahl2 = 'J';
	do
	{   
		int messwerte = 0;       //Werte
		int einfuegewerte = 0;   //für die automatischen Werte
		int nCount = 0;          //Mitzähler
		int suche = 0;           //für suche
		int search = 0;          //für suche
		int info = 0;            //wird benötigt zusäzlich zu den Werten
		int durchschnittswert = 0;  //für Berechnung
		int merker=3; 

		//Baum
		node* root = new node;   
		node* z = new node;      

		//Bauminetialisiereung
		treeinitialize(root , z);  

		//Eingabe der Zufallszahlen!
		system("cls");
		cout <<"Anzahl der Zufallszahlen: ";
		cin >> nCount;

		// Eingabe muss positiv sein!
		if (nCount < 0)    
		{
			do
			{
				cout <<endl;
				cout <<"Die Eingabe muss positiv sein!\n\n";
				cout <<"Anzahl der Zufallszahlen: ";
				cin >> nCount;

			}while (nCount < 0);
		}

		// Dynamisches array erstellen
		int* nKeys = new int[nCount];  

		// Zufallszahlen erstellen
		srand(GetTickCount());    

		//Array mit Zufahlszahlen befüllen
		for (int i = 0; i<nCount; i++)  
		{
			nKeys[i] = rand() % (nCount*5);
		}

		// Ausgabe der arry Zahlen
		cout << endl;                     
		cout <<"Zahlen im Array!\n\n";

		for(int j = 0; j < nCount; j++) 
		{
			cout << nKeys[j] <<" ";
		} 

		// Sortierung mit Selection (Aufsteigend)
		selection(nKeys, nCount);   

		//Befüllen des Baumes mit automatisch generierten Zahlen
		for(int k = 0; k < nCount; k++) 
		{

			einfuegewerte = nKeys[k];
			info ++;

			treeinsert(root, z, einfuegewerte, info);

		} 

		//Löschen des nicht mehr nötigen dynamischen Arrays
		delete nKeys;

		//Ausgabe der Daten mit Inorder (Aufsteigend)
		cout << endl;
		cout <<"--------------------\n";
		cout <<"Inorder-Traverse:\n";
		cout <<"--------------------\n";
		TreePrintInorder(root->r, z);      

		//Ausgabe der Daten mit Preorder
		cout << endl;
		cout <<"--------------------\n";
		cout <<"Preorder-Traverse:\n";
		cout <<"--------------------\n";
		TreePrintPreorder(root->r, z);

		//Ausgabe der Daten mit Postorder (Absteigend)
		cout << endl;
		cout <<"--------------------\n";
		cout <<"Postorder-Traverse:\n";
		cout <<"--------------------\n";
		TreePrintPostorder(root->r, z);

		//Ausgabe der Daten mit Postorder (Absteigend)
		cout << endl;
		cout <<"-----------------------\n";
		cout <<"Die groessten 3 Zahlen:\n";
		cout <<"-----------------------\n";
		TreePrint3Postorder(root, z, &merker);

		//Zahl suchen (ob vorhanden oder nicht)
		cout <<"\n\n";
		cout <<"Geben sie den zu suchende Zahl ein: ";
		cin >> suche;

		search = treesearch(root , z, suche);

		if (search == -1)   // wenn nicht gefunden
		{
			cout <<endl;
			cout<< "Nicht gefunden!\n";
		}
		else                // wenn gefunden
		{
			cout <<endl; 
			cout << "Gefunden! " <<endl;
		}

		//Berechnen des Durchschnittswert
		durchschnitt(root->r, z, durchschnittswert);
		cout << endl;
		if (durchschnittswert == 0)   //wenn nichts in der Liste
		{
			cout << endl;
			cout <<"Keine Werte eingegeben!\n";

		}
		else                         //sonnst
		{
			cout <<"Der Druchschnittswert ist: " << durchschnittswert/info << endl;
			durchschnittswert = 0;

		}

		//Baum komplett löschen
		deleteall(root->r,z);
		root->r = z;
		info = 0; 
		cout << endl;
		cout <<"Alle Daten geloescht!\n";

		//Programm noch einmal ausführen?
		cout << endl;
		cout << endl;
		cout <<"Wollen Sie das Programm noch mal ausfuehren? (J/N)\n"; 
		cin >> auswahl2;
		cout << endl;

		//Löschen des dynamischen Speichers
		delete root;
		delete z;

		//Abbruchbedingung
	}while ( auswahl2 == 'j' || auswahl2 == 'J');  

	_getch();
}

// Selection sortierung (Aufsteigend)
void selection(int nKeys[], int nCount)  
{
	int i, j, min, t = 0;

	for(i = 0; i < nCount; i++) 
	{
		min = i;

		for(j = i+1; j < nCount; j++)
			if(nKeys[j] < nKeys[min])
				min = j;

		t = nKeys[min];
		nKeys[min] = nKeys[i];
		nKeys[i] = t;
	}

	// Ausgabe der Sortierten Zahlen
	cout <<"\n\n";                     
	cout <<"Zahlen Sortiert im Array!\n\n";

	for(i = 0; i < nCount; i++) 
	{
		cout << nKeys[i] <<" ";
	} 
	cout << endl;
}

//Bauminetialisiereung
void treeinitialize(node *root , node* z)
{
	z->l = z; 
	z->r = z; 
	z->info = -1;
	z->messwerte = -1;

	root->r = z; 
	root->l = z;
	root->messwerte = 0;
	root->info = 0;
}

//Einfügen der Elemente in den Baum
void treeinsert(node* root, node* z, int messwerte, int info)
{
	node *p, *x;
	p = root; 
	x = root->r;

	while(x != z)
	{
		p = x;
		if(messwerte < x->messwerte)
			x = x->l;
		else
			x = x->r;
	}

	x = new node;
	x->messwerte = messwerte; 
	x->info = info; 
	x->l = z; 
	x->r = z;

	if(messwerte < p->messwerte)
		p->l = x;
	else
		p->r = x;
}

//Ausgabe Inorder (Aufsteigende sortierung , Alphabet)
void TreePrintInorder(node *root , node* z) 
{                                          
	if (root != z)
	{
		TreePrintInorder(root->l, z);
		cout << root->messwerte <<" ";
		TreePrintInorder(root->r, z);
	}
}

// Ausgabe Prorder (WLR)
void TreePrintPreorder(node *root, node* z) 
{
	if (root != z)
	{
		cout <<root->messwerte <<" ";
		TreePrintPreorder(root->l, z);
		TreePrintPreorder(root->r, z);
	}
}

//Ausgabe Postorder (Absteigende Sortierung)
void TreePrintPostorder(node *root, node* z) 
{
	if (root != z)
	{
		TreePrintPostorder(root->l, z);
		TreePrintPostorder(root->r, z);
		cout <<root->messwerte <<" ";
	}
}
//Ausgabe der größten 3 Zahlen
void TreePrint3Postorder(node *root, node* z, int* nochAuszugeben)
{
	if(*nochAuszugeben==0) return;
	if (root != z)
	{
		TreePrint3Postorder(root->l, z, nochAuszugeben);
		TreePrint3Postorder(root->r, z, nochAuszugeben);
		if(*nochAuszugeben==0) return;

		cout <<root->messwerte <<" ";
		--*nochAuszugeben;
	}
}

void TreePrint3Postorder(node *root, node* z, int nochAuszugeben)
{
	TreePrint3Postorder(root, z, &nochAuszugeben);
} 

//Suche im Baum nach einem Wert
int treesearch(node* root, node* z, int suche)
{
	node *x = root->r;
	z->messwerte = suche;

	while(suche != x->messwerte)
	{	
		if(suche < x->messwerte)
			x = x->l;
		else
			x = x->r;
	}
	return x->info;
}

//Berechnung für einen Durchschnittswert
//Zusammenzählen der Werte mit Hilfe der Inorder Ausgabe
void durchschnitt(node *root , node* z, int& durchschnittswert) 
{
	if (root != z)
	{
		durchschnitt(root->l, z,durchschnittswert);
		durchschnittswert += root->messwerte;
		durchschnitt(root->r, z,durchschnittswert);
	}
}

//Löschen des gesammten Baumes
void deleteall(node *root, node *z)
{
	if (root->l != z)
		deleteall(root->l, z); 

	if (root->r != z)
		deleteall(root->r, z);  
}

[Gast]

Ach Compiler-Fehler... Hab ich gar nicht bemerkt...

Wenn ich das im hauptprogramm auf 3 setze geht es nicht leider.

Mit Fehlermeldung des Compilers oder wenigstens
der Angabe "kompiliert nicht" wäre mir das auch aufgefallen

[Gast]

volkard schrieb:

CSpille schrieb:

Aber eigentlich wollte ich Fragen, warum du einen Zeiger auf nochAuszugeben der Referenz vorziehst?
Hat das einen Grund oder nur 'Zufall'? Denn Referenzen haben (wie ich finde)
eine übersichtlichere Syntax.

Weil ich reinschreibe. Ich optimiere für den Aufrufer, nicht für das Werkzeug. Der Aufrufer muß sehen, daß da eine Veränderung der Variablen geplant ist.

Aber ich hab schon dran gedacht, hier aus Faulheit mal schnell eine Referenz zu nehmen. Dann ist mir aber eingefallen, daß michael_xsx drum gebettelt hat, noch ein wenig mit Zeigern üben zu dürfen. Da hab ich's ihm halt besorgt.

Klingt sehr plausibel!!! DANKE für die Info!

Ich gehe mal davon aus, dass du bei Objekten solche Angelegenheiten per const
regelst. Verwendest du denn in irgendeinem Fall Referenzen auf einfache Datentypen als Parameter?

[volkard]

Ich könnte mir vorstellen, daß das mit einem int als Parameter und einem int als Rückgabewert, wieviel noch zu machen ist, viel hübscher wäre und dann würde auch wieder eine Funktion ausreichen und alles noch ein bißchen superer.

[volkard]

CSpille schrieb:

Verwendest du denn in irgendeinem Fall Referenzen auf einfache Datentypen als Parameter?

Ich glaube nicht.