Baum Problem

Hi,
ich hab ein Problem mit Bäumen -arbeite mich da gerade erst ein- und zwar möchte ich in einen Baum etwas einfügen und zwar möchte ich nichts nach groß/klein sortieren sondern einfach der Reihe nach immer rein: Links frei -> Nach Links ansonsten Rechts...

Hier mein Code:

CPP:

#include "SymTable.h"

SymTableNode::SymTableNode( const SymTableValue &Val ) : Left( NULL ), Right( NULL ), Value ( Val )
{
}

SymTableNode::~SymTableNode( void )
{
	if ( Left ) { printf( "L: %s\n", Left->Value.Str); delete Left; }
	if ( Right ) { printf( "R: %s\n", Right->Value.Str); delete Right; }
}

void SymTableNode::Insert( const SymTableValue &Val )
{
	if ( ( Left == NULL ) || ( Right == NULL ) )
	{
		if ( Left == NULL )
		{
			if ( Left != NULL )
			{
				Left->Insert( Val );
				return;
			}

			Left = new SymTableNode( Val );
			return;
		}
		else if ( Right == NULL )
		{
			if ( Right != NULL )
			{
				Right->Insert( Val );
				return;
			}

			Right = new SymTableNode( Val );
			return;
		}
		else
		{
			printf( "%i: Und nun!?\n", __LINE__ );
		}
	}
	else
	{
		printf( "%i: Und nun!?\n", __LINE__ );
	}
}

Header:

#ifndef SYM_TABLE_H
#define SYM_TABLE_H

#include <stdio.h>

struct SymTableValue
{
	union 
	{ 
		char *Str;
	};

	SymTableValue()
	{
		Str = NULL;
	}
};

class SymTableNode
{
	private:
		SymTableValue Value;
		SymTableNode *Left;
		SymTableNode *Right;
	public:
		SymTableNode( const SymTableValue &Val );
		virtual ~SymTableNode( void );
		void Insert( const SymTableValue &Val );
		SymTableNode *GetLeft( void ) { return Left; } 
		SymTableNode *GetRight( void ) { return Right; } 
};

class SymTable
{
	private:
		SymTableNode Node;
	public:
		void Insert( void );
};

#endif /* SYM_TABLE_H */

Es mangelt mir ein wenig am Verständnis... Wäre über Hilfe dankbar, denn es wird
nach 2 Werten nichts mehr eingeordnet...

Danke

Gruß

Javaner

Das ist ja auch kein Wunder.

Du schreibst

if ( ( Left == NULL ) || ( Right == NULL ) )

nach dem 2. Aufruf sind nunmal Left und Right beide != Null
und du fügst nichts mehr ein.

Ansonsten ist deine Aufgabenstellung, immer nur links einzufügen
sowieso nicht sinnvoll.

Hmm,
ich wollte eigentlich immer komplett füllen also erst links dann rechts dann in dann das gleiche in den dadurch neu enstandenen Knoten, aber da hab ich so meine Probleme. Wie mache ich das richtig?

Werner Salomon

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