proggen.org

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;
}

Code: Alles auswählen

int main( void )
{
  struct BinaryTreeRoot * root = malloc( sizeof( struct BinaryTreeRoot ) );
  struct BinaryTree * element = NULL;

  int init[] = { 3,7,8,2,6,4,5,2,9, -1 };
    int i=0;

  /* Initialisation */

  printf( "\n--- Initialisierung--------------------------\n\n" );

  while( init[i] >= 0 )
  {
    element = CreateElement( init[i] );
    if( element )
      insert( root, element );

    i++;
     printf( "\n--- %d\n\n",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;
}