Hier wird ein binärer Suchbaum erstellt und damit rumgespielt. Ihr braucht das Wörter buch das ihr auf Prof. Bittel Seite findet: Deutsch-Englisch Wörterbuch
Programmiertechnik 2 – Aufgabe 6 (Wörterbuch als binärer Suchbaum)
Lösung:
main.cpp
// BinarySearchTreeMain.cpp
// A. Giemza, HTWG KN
// Erstellt: 16.06.2010
#include <iostream>
#include <fstream>
#include <cstdlib>
#include "BinarySearchTree.h"
int main(int argc, char *argv[])
{
typedef string Deutsch;
typedef string Englisch;
BinarySearchTree<Deutsch, Englisch> deen;
BinarySearchTree<Deutsch, Englisch> ende;
ifstream dtengl("dtengl.txt");
string deu,eng;
for (int i = 0; i < atoi(argv[1]); i++)
{
dtengl >> deu >> eng;
deen.insert(deu, eng);
ende.insert(eng, deu);
}
dtengl.close();
cout << "Deutsch-Englisch Statistik:" << endl;
deen.statistik();
cout << "Englisch-Deutsch Statistik:" << endl;
ende.statistik();
cout << "Deutsch-Englisch Ausgabe:" << endl;
deen.prettyPrint();
cout << "Englisch-Deutsch Ausgabe:" << endl;
ende.prettyPrint();
cout << "Deutsch-Englisch durchmischen ..." << endl << endl;
deen.balance();
cout << "Deutsch-Englisch Statistik (nach balance()):" << endl;
deen.statistik();
cout << "Deutsch-Englisch Ausgabe(nach balance()):" << endl;
deen.prettyPrint();
return 0;
}
BinarySearchTree.h
// BinarySearchTree.h
//
// Class BinarySearchTree
//
// O.Bittel, HTWG KN
// Erstellt: 22.09.2005
// Geandert: 18.10.2006
// Geandert: 24.05.2007
// A. Giemza, HTWG KN
// Erweitert: 16.06.2010
#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H
#include <vector>
#include "BinarySearchTree.h"
using namespace std;
template <class KeyType, class ValueType>
// KeyType erfordert Vergleichsoperatoren <, ==, und >
// ValueType erfordert Zuweisungsoperator =
class BinarySearchTree
{
public:
BinarySearchTree() {root = 0;}
~BinarySearchTree() {makeEmptyR(root);}
void traverse() const {traverseR(root);}
// Travesiert ueber alle Schlssel in sortierter Reihenfolge
// und gibt gibt Daten aus.
bool search(const KeyType& k, ValueType& v) const {return searchR(k,v,root);}
// sucht Schluessel k und liefert Wert v falls gefunden.
// Gibt true zurueck, falls Schlssel k gefunden wird, und sonst false.
bool insert(const KeyType& k, const ValueType& v) {return insertR(k,v,root);}
// Fuegt neuen Schlssel k mit Wert v ein.
// Falls Schlssel bereits vorhanden ist, wird nicht eingefgt und
// false zurckgeliefert, sonst true.
bool remove(const KeyType& k) {return removeR(k,root);}
// L�cht Schlssel k.
// Falls Schlssel gel�cht werden konnte wird true zurckgeliefert
// und sonst false (d.h. Schlssel war nicht vorhanden).
// eigene
void statistik();
void prettyPrint();
void balance();
private:
// Knoten fr Bin�baum:
struct Node
{
KeyType key;
ValueType value;
Node* left;
Node* right;
// Konstruktoren
Node() : left(0), right(0) {}
Node(const KeyType& k, const ValueType& v) : key(k), value(v), left(0), right(0) {}
};
Node* root;
// Rekursive, private Methoden:
void traverseR(const Node* p) const;
bool searchR(const KeyType& k, ValueType& v, const Node* p) const;
bool insertR(const KeyType& k, const ValueType& v, Node*& p);
bool removeR(const KeyType& k, Node*& p);
// Hilfsmethode fr removeR
void getRemoveMin(KeyType& k, ValueType& v, Node*& p);
void makeEmptyR(Node* p);
// eigene
void statistikR(Node* in,int &anzahl,int &hoehe, double &durch);
void prettyPrintR(Node* in);
void saveR(const Node* p, vector<KeyType>& keys, vector<ValueType>& values);
void readR(int li, int re, vector<KeyType>& keys, vector<ValueType>& values);
};
template <class KeyType, class ValueType>
void BinarySearchTree<KeyType, ValueType>::traverseR(const Node* p) const
// Gibt alle Elemente in Infix-Reihenfolge aus.
{
if (p != 0)
{
traverseR(p->left);
cout << p->key << ": " << p->value << endl;
traverseR(p->right);
}
}
template <class KeyType, class ValueType>
bool BinarySearchTree<KeyType, ValueType>::searchR(const KeyType& k, ValueType& v, const Node* p) const
// Sucht nach einem Knoten mit Schlssel k im Teilbaum p.
// Falls gefunden, wird der im Knoten abspeicherte Wert v
// und der Rckgabewert true zurckgeliefert.
// Falls nicht gefunden, wird der Rckgabewert false zurckgeliefert.
{
if (p == 0)
return false;
else if (k < p->key)
return searchR(k,v,p->left);
else if (k > p->key)
return searchR(k,v,p->right);
else // k gefunden
{
v = p->value;
return true;
}
}
template <class KeyType, class ValueType>
bool BinarySearchTree<KeyType, ValueType>::insertR(const KeyType& k, const ValueType& v, Node*& p)
// Fgt im Teilbaum p neuen Knoten mit Schlssel k und Datenwert v ein.
// Falls Schlssel schon vorhanden, wird kein neuer Knoten eingefgt.
// Rckgabewert gibt an, ob eingefgt wurde.
// Da der bergebene Teilbaum p ge�dert werden muss, ist p Referenzparameter.
{
if (p == 0)
{
p = new Node(k,v);
return true;
}
else if (k < p->key)
return insertR(k,v,p->left);
else if (k > p->key)
return insertR(k,v,p->right);
else // k bereits vorhanden
return false;
}
template <class KeyType, class ValueType>
bool BinarySearchTree<KeyType, ValueType>::removeR(const KeyType& k, Node*& p)
// L�cht im Baum p Knoten mit Schlssel k.
// Rckgabewert gibt an, ob gel�cht wurde.
// Da der bergebene Teilbaum p ge�dert werden muss, ist p Referenzparameter.
{
if (p == 0) // k nicht vorhanden
return false;
else if (k < p->key)
return removeR(k,p->left);
else if (k > p->key)
return removeR(k,p->right);
else if (p->left == 0 || p->right == 0) // Gefundenes k hat ein oder kein Kind
{
Node* temp = p;
if (p->left != 0)
p = p->left; // Bypass zu linkes Kind
else
p = p->right; // Bypass zu rechtes Kind
delete temp;
return true;
}
else // Gefundenes k hat zwei Kinder
{
// Ersetze p mit kleinstem Knoten in rechtem Unterbaum:
KeyType k; ValueType v;
getRemoveMin(k,v,p->right);
p->key = k;
p->value = v;
return true;
}
}
template <class KeyType, class ValueType>
void BinarySearchTree<KeyType, ValueType>::getRemoveMin(KeyType& k, ValueType& v, Node*& p)
// getRemoveMin l�cht kleinstes Element im Baum p und liefert
// Wert v und Schlssel k des kleinsten Elements zurck.
{
// p muss != 0 sein.
if (p->left == 0) // Minimum gefunden
{
k = p->key;
v = p->value;
Node* temp = p;
p = p->right;
delete temp;
}
else
getRemoveMin(k,v,p->left);
}
template <class KeyType, class ValueType>
void BinarySearchTree<KeyType, ValueType>::makeEmptyR(Node* p)
// Gibt Speicherplatz fr kompletten Baum p frei.
{
if (p != 0)
{
makeEmptyR(p->left);
makeEmptyR(p->right);
delete p;
}
}
template <class KeyType, class ValueType>
void BinarySearchTree<KeyType, ValueType>::statistik()
{
int hoehe = 0, anzahl = 0;
double durch = 0;
if(root != 0)
{ // ruft zaehlende Funktion auf
statistikR(root, anzahl, hoehe, durch);
}
durch = durch/anzahl; // Berechnung der Durchschnittstiefe
// Ausgabe der Daten
cout << "Anzahl der Eintraege im Baum : " << anzahl << endl
<< "die Hoehe des Baumes : " << hoehe << endl
<< "die durchschnittliche Tiefe aller Eintraege: " << durch << endl << endl;
}
template <class KeyType, class ValueType>
void BinarySearchTree<KeyType, ValueType>::statistikR(Node* in, int &anzahl, int &hoehe, double &durch)
{
static int tempHoehe=-1;
if(in != 0)
{
tempHoehe++;
// Bestimmung aktueller Hoehe des Baumes
if(tempHoehe > hoehe)
{
hoehe = tempHoehe; // Bestimmung der absoluten Hoehe
}
anzahl++; // zaehlt Knoten
statistikR(in->left, anzahl, hoehe, durch); // durchlaeuft linken Teil
statistikR(in->right, anzahl, hoehe, durch); // durchlaeuft rechten Teil
durch += tempHoehe; // Hoehensumme aller Knoten - ermoeglicht Durchschnittsberechnung
tempHoehe--; // Bestimmung aktueller Hoehe des Baumes
}
}
template <class KeyType, class ValueType>
void BinarySearchTree<KeyType, ValueType>::prettyPrint()
{
if(root != 0) // Falls Baum nicht leer
prettyPrintR(root); // Hilfsfunktion, rekursiver Aufruf
cout << endl;
}
template <class KeyType, class ValueType>
void BinarySearchTree<KeyType, ValueType>::prettyPrintR(Node* in)
{
static int tiefe = -1; // Rekursionstiefe
tiefe++;
for (int i = 1; i < tiefe; i++) // Ermoeglicht Baumstruktur
cout << " ";
if (tiefe > 0)
cout << "|__";
if (in != 0) // Ausgabe der Daten wenn in != 0
{
cout << in->key << 'n';;
if (in->left != 0 || in->right != 0) // rekursive Aufrufe wenn mindestens ein Folgeknoten existiert
{
prettyPrintR(in->left);
prettyPrintR(in->right);
}
}
else // wenn in == 0, Ausgabe von # - Kein Folgeknoten
{
cout << "#n";
}
tiefe--;
}
template <class KeyType, class ValueType>
void BinarySearchTree<KeyType, ValueType>::balance()
{
vector<KeyType> keys; // Vector fuer Schluessel
vector<ValueType> values; // Vector fuer Daten
saveR(root, keys, values); // Datensaetze in den beiden Vectors abspeicher
makeEmptyR(root); // Baum leeren
root = 0;
readR(0, keys.size() - 1, keys, values); // Datensaetze wieder einfuegen
}
template <class KeyType, class ValueType>
void BinarySearchTree<KeyType, ValueType>::saveR(const Node* in, vector<KeyType>& keys, vector<ValueType>& values)
{
if (in != 0)
{
saveR(in->left, keys, values); // speichere linkten Teilbaum
keys.insert(keys.end(), in->key); // speichere Schluessel und Daten
values.insert(values.end(), in->value);
saveR(in->right, keys, values); // speichere rechten Teilbaum
}
}
template <class KeyType, class ValueType>
void BinarySearchTree<KeyType, ValueType>::readR(int li, int re, vector<KeyType>& keys, vector<ValueType>& values)
{
if (re >= li) // wenn Feld nicht leer
{
int m = li + (re - li + 1) / 2; // bestimme mittleren Index zwischen li und re
insert(keys[m], values[m]); // lese mittleren Datensatz
readR(li, m-1, keys, values); // lese linken Teilbaum
readR(m+1, re, keys, values); // lese rechten Teilbaum
}
}
#endif
makefile
# File: Makefile fuer BinarySearchTree # Author: Oliver Bittel # Date: 24.05.2007 # Definitions: CC = g++ -g # -g wird nur fr Debugger benoetigt! OBJ = main.o BIN = main # Rules: $(BIN): $(OBJ) $(CC) -o $(BIN) $(OBJ) main.o: main.cpp BinarySearchTree.h $(CC) -c main.cpp