Ich werde den Code mal als Vergleich rein - er ist bisher weder sinnvoll getestet, noch sonstwas, nur um mal drüberzusehen.
Code: Alles auswählen
#include <stdio.h>
#include <stdlib.h>
struct BinaryTreeRoot
{
struct BinaryTree * RootElement;
};
struct BinaryTree
{
struct BinaryTree *Superiour;
struct BinaryTree *Left, *Right;
int Key;
};
struct BinaryTree * CreateElement( int key )
{
struct BinaryTree * result = malloc( sizeof( struct BinaryTree ) );
if( result )
{
result->Superiour = NULL;
result->Left = NULL;
result->Right = NULL;
result->Key = key;
}
return result;
}
/* Arguments must be valid! */
void insertElement( struct BinaryTree * super, struct BinaryTree * element )
{
if( super->Key < element->Key )
if( super->Left )
insertElement( super->Left, element );
else
{
super->Left = element;
element->Superiour = super;
}
else
if( super->Right )
insertElement( super->Right, element );
else
{
super->Right = element;
element->Superiour = super;
}
}
/* Arguments must be valid! */
void insert( struct BinaryTreeRoot * root, struct BinaryTree * element )
{
if( root->RootElement == NULL )
root->RootElement = element;
else
if( root->RootElement->Key < element->Key )
if( root->RootElement->Left )
insertElement( root->RootElement->Left, element );
else
{
root->RootElement->Left = element;
element->Superiour = root->RootElement;
}
else
if( root->RootElement->Right )
insertElement( root->RootElement->Right, element );
else
{
root->RootElement->Right = element;
element->Superiour = root->RootElement;
}
}
void PrintTreeInternal( struct BinaryTree * element, int indent, char from )
{
if( element )
{
PrintTreeInternal( element->Left, indent + 1, 'l' );
int i;
for( i = 0; i < indent; i++ )
printf( " " );
switch( from )
{
case 'l': printf( "/-> %d\n", element->Key ); break;
case 'r': printf( "\\-> %d\n", element->Key ); break;
default: printf( "--> %d\n", element->Key ); break;
}
PrintTreeInternal( element->Right, indent + 1, 'r' );
}
}
/* Arguments must be valid! */
void PrintTree( struct BinaryTreeRoot * root )
{
PrintTreeInternal( root->RootElement, 0, '-' );
}
struct BinaryTree * Search( struct BinaryTreeRoot * root, int key )
{
struct BinaryTree * result = root->RootElement;
while( result )
{
if( result->Key == key )
break;
if( result->Key < key )
result = result->Left;
else result = result->Right;
}
return result;
}
void DeleteElement( struct BinaryTreeRoot * root, struct BinaryTree * element, int recursive )
{
if( recursive )
{
if( element->Left ) DeleteElement( root, element->Left, 1 );
if( element->Right ) DeleteElement( root, element->Right, 1 );
}
else
{
if( element->Superiour == root->RootElement )
root->RootElement = NULL;
else if( element->Superiour->Left == element )
element->Superiour->Left = NULL;
else
element->Superiour->Right = NULL;
if( element->Left ) insert( root, element->Left );
if( element->Right ) insert( root, element->Right );
free( element );
}
}
void Delete( struct BinaryTreeRoot * root, int key, int recursive )
{
struct BinaryTree * result = Search( root, key );
if( result )
{
DeleteElement( root, result, recursive );
}
}
int main( void )
{
struct BinaryTreeRoot root;
struct BinaryTree * element;
int init[] = { 3,7,8,2,6,4,5,2,9, -1 };
/* Initialisation */
printf( "\n--- Initialisierung--------------------------\n\n" );
int i=0;
while( init[i] >= 0 )
{
element = CreateElement( init[i] );
if( element )
insert( &root, element );
i++;
}
printf( "\n--- Ausgabe ---------------------------------\n\n" );
PrintTree( &root );
printf( "\n--- Suche -----------------------------------\n\n" );
element = Search( &root, 4 );
printf( "gefunden: %d\n", ( element == NULL ) ? -1 : element->Key );
element = Search( &root, 14 );
printf( "gefunden: %d\n", ( element == NULL ) ? -1 : element->Key );
printf( "\n--- Löschen---------------------------------\n\n" );
Delete( &root, 6, 0 );
printf( "\n--- Ausgabe ---------------------------------\n\n" );
PrintTree( &root );
return 0;
}
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.
Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.
