Tripletree (einlesen/ausgeben inorder)

xMänneken

Moin,

ich habe probiert einen Tripletree zu programmieren.
Der soll kleinere Zeichen im linken, gleiche im mittleren und größere im rechten Ast speichern.

Die Funktion insert(char) soll ein Zeichen einfügen und traverse() soll den Baum inorder Ausgeben.

insert funzt eigentlich soweit ganz gut, nur die Wurzel hab ich bisher noch unschön im Konstruktor integriert...naja, mit traverse hapert es noch..könnt ihr mir da Tips geben ?

Die Ausgabe müßte (laut den Chars unten im Code) ja wie folgt aussehen:
AABCDDGGHN.

Dank für Hinweise!!

#include <iostream>
using namespace std;

class tree
{
	public:

	struct knoten
	{
		public:

		char inhalt;
		knoten* kleiner;
		knoten* gleich;
		knoten* groesser;
	};

	knoten* start; // Wurzel
	knoten* aktuell; // "Cursor" für den aktuellen Knoten
	knoten** helf; // "merkt" sich den letzen Knoten

	tree(); // Konstruktor

	void insert(char zeichen) // Anfang insert
	{

		if(aktuell == NULL)
		{
			cout << "Eingefuegt: " << zeichen << "\n"; // nur zur Überprüfung
			aktuell = new knoten;
			aktuell->inhalt = zeichen;
			aktuell->kleiner = NULL;
			aktuell->gleich = NULL;
			aktuell->groesser= NULL;

			*helf = aktuell;

			aktuell = start; // setzt "aktuell" nach dem Einfügen wieder auf die Wurzel
		}

		else
		{

			if(zeichen < aktuell->inhalt)
			{ 
				helf = &(aktuell->kleiner);
				aktuell = aktuell->kleiner;
				cout << "Zeichen ist kleiner ";
				insert(zeichen);
			}

			else
			{
				if(zeichen > aktuell->inhalt)
				{
					helf = &(aktuell->groesser);
					aktuell = aktuell->groesser;
					cout << "Zeichen ist groesser ";
					insert(zeichen);
				}
			}

			if(zeichen == aktuell->inhalt)
			{
				helf = &(aktuell->gleich);
				aktuell = aktuell->gleich;
				cout << "Zeichen ist gleich ";
				insert(zeichen);
			}
		}

	} // Ende insert

	void traverse() // Anfang traverse
	{ 

		if(aktuell->kleiner != NULL)
		{
			aktuell = aktuell->kleiner;
			traverse();
		}

		if(aktuell->gleich != NULL)
		{
			aktuell = aktuell->gleich;
			traverse();
		}

		cout << "  " << aktuell->inhalt;

		if(aktuell->groesser != NULL)
		{
			aktuell = aktuell->groesser;
			traverse();
		}

	} // Ende traverse()

	~tree(); // Destruktor
};

tree::tree() // Konstruktor mit Wurzel
{
	start = new knoten;
	start->kleiner = NULL;
	start->gleich = NULL;
	start->groesser = NULL;
	start->inhalt = 'D';
	aktuell = start;
}

tree::~tree()
{}

int main()
{
	tree *baum = new tree();

	baum->insert('A');
	baum->insert('G');
	baum->insert('H');
	baum->insert('B');
	baum->insert('N');
	baum->insert('C');
	baum->insert('D');
	baum->insert('A');
	baum->insert('G');

	baum->traverse();

        return 0;

}

Fellhuhn

void traverse() // Anfang traverse
    {

        if(kleiner != NULL)
        {
            kleiner->traverse();
        }

        if(gleich != NULL)
        {
            gleich->traverse();
        }

        cout << "  " << inhalt;

        if(groesser != NULL)
        {
            groesser->traverse();
        }

    } // Ende traverse()

Fellhuhn

So wäre aber besser:

#include <iostream>

template<typename T>
class Node{
private:
    T value;

    Node *smaller;
    Node *equal;
    Node *larger;

public:
    Node(const T &a) : value(a), smaller(0), equal(0), larger(0){

    }    
    virtual ~Node(){ 
	if (smaller) delete smaller;
	if (equal) delete equal;
	if (larger) delete larger;
    }

    void insert(const T &a){
	if (a < value){
	    if (!smaller) smaller = new Node(a);
	    else smaller->insert(a);
	}
	else if (a == value){
	    if (!equal) equal = new Node(a);
	    else equal->insert(a);
	}
	else{
	    if (!larger) larger = new Node(a);
	    else larger->insert(a);
	}
    }
    void print(){
	if (smaller) smaller->print();
	if (equal) equal->print();
	std::cout << " " << value;
	if (larger) larger->print();
    }    
};

template<typename T>
class Tree{
private:    
    Node<T> *root;

public:
    Tree() : root(0){}
    virtual ~Tree(){ if (root) delete root; }

    void insert(const T &a){
	if (root) root->insert(a);
	else root = new Node<T>(a);
    }
    void print(){
	if (root){
	    root->print();
	    std::cout << std::endl;
	}
	else std::cout << "<empty>" << std::endl;
    }
};

int main(int argc, char *argv[]){
    Tree<char> tree;

    tree.insert('a');
    tree.insert('n');
    tree.insert('r');
    tree.insert('f');
    tree.insert('k');
    tree.insert('l');

    tree.print();
}

1. Mit Templates kannst du das Ding auch mit allen anderen Datentypen benutzen
2. Mit Destruktor hast du keine Speicherlecks.
3. Durch Splittung in Node und Tree kannst du auch einen leeren Baum haben.

Tyrdal

Was soll denn das if(smaller) usw. vor dem delete im Node-Destruktor?

Fellhuhn

Tyrdal schrieb:

Was soll denn das if(smaller) usw. vor dem delete im Node-Destruktor?

Das überprüft ob der Pointer nicht Null ist. Ansonsten fliegt dir das um die Ohren.

Airdamn

bei delete 0 fliegt nix herum

asc

Fellhuhn schrieb:

Tyrdal schrieb:

Was soll denn das if(smaller) usw. vor dem delete im Node-Destruktor?

Das überprüft ob der Pointer nicht Null ist. Ansonsten fliegt dir das um die Ohren.

Ein delete auf einen NULL-Zeiger ist nach dem Standard definiert (=es passiert nichts).

Das einzige was dir um die Ohren fliegen kann sind uninitialisierte Zeiger die auf eine zufällige Adresse (!=0) verweisen. Und dagegen kann dein if auch nicht schützen.

cu André

Fellhuhn

Tatsächlich? Ist mir neu. Gut zu wissen.

Was willst Du eigentlich mit dieser Baumstruktur anstellen? Nicht dass das std::priority_queue das für Dich erledigen kann.