W
BraucheHilfe schrieb:
ich wollte eigentlich immer komplett füllen also erst links dann rechts dann in dann das gleiche in den dadurch neu enstandenen Knoten
Also wenn ich das wörtlich nehme, soll ein Baum mit z.B. 10 Elementen so
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /
8 9 10
aussehen. Wobei jede Zahl für ein Element steht. Die 1 für das Element, welches als erstes mit 'insert' aufgenommen wurde; die 2 für das nächste aufgenommenen usw.
BraucheHilfe schrieb:
.., aber da hab ich so meine Probleme. Wie mache ich das richtig?
Das wiederum ist 'ne richtige Denksportaufgabe; ich habe eine Weile gebraucht, bis ich eine 'einfache' Lösung gefunden habe. Die Idee dabei ist, dass jeder Knoten implizit eine Nummer besitzt und die Nummer des jeweiligen Parent-Knoten jeweils halb so groß ist. Im ganzen sieht es dann so aus:
#include <cassert>
template< typename T >
class SymTable
{
class Node
{
public:
explicit Node( const T& x )
: m_left( 0 ), m_right( 0 ), m_value( x )
{}
~Node()
{
delete m_left;
delete m_right;
}
static Node*& get( Node*& root, int nr )
{
if( nr == 1 ) return root; // Root hat die Nummer 1
Node* parent = get( root, nr/2 ); // 'nr/2' ist der Vater von 'nr'
assert( parent ); // dieser muss da sein, sonst gibt's auch kein Kind
return nr%2 == 0? parent->m_left: parent->m_right;
}
private:
Node* m_left;
Node* m_right;
T m_value;
};
public:
SymTable() : m_root( 0 ), m_cnt( 0 ) {}
~SymTable() { delete m_root; }
void insert( const T& x )
{
Node*& p = Node::get( m_root, ++m_cnt ); // Knoten mit der Nummer m_cnt+1 besorgen
assert( p == 0 ); // der Knoten ist neu, darf also noch nicht da sein
p = new Node( x );
}
private:
Node* m_root;
int m_cnt; // aktuelle Anzahl der Elemente im Baum
SymTable( const SymTable& ); // -- Kopieren verhindern
SymTable& operator=( const SymTable& );
};
Ich habe mir noch erlaubt das 'SymTableValue' durch den Template-Parameter T zu ersetzen und (SymTable)Node ist eine sogenannte nested class von SymTable.
Falls man jetzt noch zum Node die Ausgabe-Funktion - ab Zeile 25 (s.o.) -
static void print( const Node* nd, std::ostream& out, int indent )
{
const int TAB_WIDTH = 4;
if( nd == 0 ) return;
print( nd->m_right, out, indent + TAB_WIDTH );
if( indent ) out << std::setw(indent) << out.fill();
out << nd->m_value << std::endl;
print( nd->m_left, out, indent + TAB_WIDTH );
}
hinzufügt und SymTable mit dem <<-operator für ostream versieht (Zeile 42),
friend std::ostream& operator<<( std::ostream& out, const SymTable& st )
{
Node::print( st.m_root, out, 0 );
return out;
}
- nicht zu vergessen #include <iostream> und <iomanip> - so kann man dann folgende kleine Demo zum Laufen bringen.
#include "SymTable.h" // s.o.
#include <iostream>
#include <string>
int main()
{
using namespace std;
const char* txt[] = { "eins", "zwei", "drei", "vier", "fuenf",
"sechs", "sieben", "acht", "neun", "zehn" };
SymTable< string > t;
for( const char** s = txt; s != txt + sizeof(txt)/sizeof(*txt); ++s )
t.insert( *s );
cout << t << endl;
return 0;
}
Und die Ausgabe sollte dann sein:
sieben
drei
sechs
eins
fuenf
zehn
zwei
neun
vier
acht
Der gewünschte Baum - um 90Grad nach links gedreht.
Gruß
Werner
