이중 연결 리스트 + 이진 트리(Double Linked List + Binary Tree)

/***************************************************************************
                 COPYRIGHT(c) 2010 XXX Co., Ltd.
****************************************************************************
*
*  Workfile   : DLL_And_BT.c
*  Revision   : Rev. 0.1
*  Date       : Fri Mar 26 2010, 18:59:40
*  Author     : Victor
*
****************************************************************************
*
* File Description
* ----------------
* This file is source file for "Linked List + Bynary Search Tree".
*
****************************************************************************
*
* Revision Details
* ----------------
* Rev. 0.1   Initial revision.
*
***************************************************************************/

#ifndef _LINKEDLIST_BINARYSEARCHTREE_
#define _LINKEDLIST_BINARYSEARCHTREE_
 
/***************************************************************************
 * Include Files
 **************************************************************************/
#include 
#include
 
/***************************************************************************
 *  Macros
 **************************************************************************/
// Safe free
#define RELEASEIF( a )    if(a){free(a); a=NULL;}
// Memory allocation
#define MALLOC( x )       x=(Node *)malloc(sizeof(Node));if(x == NULL){printf("   Malloc is failed!!\n");return;}
 
/***************************************************************************
 *  Define
 **************************************************************************/
#define CLS    system ( "cls"   )
#define PAUSE  system ( "pause" )

#define TRUE      1
#define FALSE     0

// Display method select
#define ALL       0
#define ONE       1

// First Search and Reverse Search
#define FORWARD   1
#define REVERSE   2

// Delete method select : First, Last, Select
#define FIRST     1
#define LAST      2
#define SELECT    3
 
/***************************************************************************
 * Type Definitions
 **************************************************************************/

// Linked List
typedef struct _Node
{
   int              m_nData;
   struct _Node    *m_pNext;
   struct _Node    *m_pPrev;
}Node;

// Binary Search Tree
typedef struct _Tree
{
   int             m_nData;
   struct _Tree   *m_pLeft;
   struct _Tree   *m_pRight;
}Tree;
 
/***************************************************************************
 *  Function Prototypes
 **************************************************************************/

// Linked List
void  LinkedList_DisplayNode     ( Node *pHead,    int nCase                                    );
void  LinkedList_AddNode         ( Node **ppHead,  Node **ppTail,    int nData,  int nPosition  );
void  LinkedList_InsertNode      ( Node **ppHead,  Node ** ppTail,   int nData,  int nTarget    );
void  LinkedList_RemoveNode      ( Node **ppHead,  Node **ppTail,    int nData,  int nPosition  );
void  LinkedList_RemoveAllNode   ( Node **ppHead                                                );
void  LinkedList_SearchNode      ( Node *pHead,    Node *pTail,      int nData,  int nSearch    );

// Binary Search Tree
void  BinaryTree_Inorder         ( Tree *pTree                                                  );
void  BinaryTree_Main            ( Tree **ppTree,  Node *pList                                  );
int   BinaryTree_CreateLeaf      ( Tree **ppTree,  int nData                                    );
void  BinaryTree_Insert          ( Tree *pTree,    Tree *pNewLeaf                               );
void  BinaryTree_RemoveAll       ( Tree **ppTree                                                );
 
//===========================================================================
// DESCRIPTION
//  "Double Linked List + Binary Search Tree" Idle
//
// PARAMETERS
//    none
//===========================================================================
int main(void)
{
   int   nSelect     = 0; // Menu Select
   int   nTemp       = 0; // Input Data
   int   nPosition   = 0; // Method Select
   int   nTarget     = 0; // Traget Data
   int   nSearch     = 0; // Search Data

   Node  *pHead      = NULL; // Head node
   Node  *pTail      = NULL; // Tail node

   Tree  *pTree      = NULL; // Binary Tree

   for(;;)
   {
      CLS;
      printf ( "\n   __________________________________\n"  );
      printf ( "   |________ Linked List TEST _______|\n"   );
      printf ( "   | Select     >>>> 1. Add          |\n"   );
      printf ( "   |            >>>> 2. Insert       |\n"   );
      printf ( "   |            >>>> 3. Search       |\n"   );
      printf ( "   |            >>>> 4. Remove       |\n"   );
      printf ( "   |            >>>> 5. Remove All   |\n"   );
      printf ( "   |            >>>> 6. Print        |\n"   );
      printf ( "   |            >>>> 7. Sort         |\n"   );
      printf ( "   |            >>>> 0. Exit         |\n"   );
      printf ( "   |_________________________________|\n"   );
      printf ( "   Enter a select Number : "                );
      scanf  ( "%d", &nSelect );

      // Program End
      if ( nSelect == 0 )
      {
         CLS;
         printf( "\n   ______________________________\n" );
         printf( "       Exit Linked List TEST \n"       );
         printf( "   ______________________________\n"   );

         LinkedList_RemoveAllNode( &pHead );
         return;
      }
      // LinkedList Add
      else if( nSelect == 1 )
      {
         CLS;
         printf( "\n   ______________________________\n" );
         printf( "      Add Linked List TEST\n"          );
         printf( "   ______________________________\n"   );

         printf( "   Enter a input Data : "              );
         scanf ( "%d", &nTemp                            );

         printf( "   First = 1 | Last = 2 :"             );
         scanf ( "%d", &nPosition                        );

         LinkedList_AddNode( &pHead, &pTail, nTemp, nPosition );
         PAUSE;
      }
      // LinkedList Insert
      else if( nSelect == 2 )
      {
         CLS;
         printf( "\n   ______________________________\n" );
         printf( "      Insert Linked List TEST\n"       );
         printf( "   ______________________________\n"   );

         printf( "   Enter a input Data : "              );
         scanf ( "%d", &nTemp                            );

         printf( "   Enter a taget Node : "              );
         scanf ( "%d", &nTarget                          );

         LinkedList_InsertNode( &pHead, &pTail, nTemp, nTarget );
         PAUSE;
      }
      // LinkedList Search
    else if( nSelect == 3 )
    {
         CLS;
         printf( "\n   ______________________________\n" );
         printf( "      Search Linked List TEST\n"       );
         printf( "   ______________________________\n"   );

         printf( "   Enter a search Data : "             );
         scanf ( "%d", &nTemp                            );

         printf( "   Forward = 1 | Reverse = 2 :"        );
         scanf ( "%d", &nSearch                          );

         LinkedList_SearchNode( pHead, pTail, nTemp, nSearch );
         PAUSE;
      }
      // LinkedList Remove
      else if( nSelect == 4 )
      {
         CLS;
         printf( "\n   ______________________________\n"    );
         printf( "      Remove Linked List TEST\n"          );
         printf( "   ______________________________\n"      );

         printf( "   First = 1 | Last = 2 | Select = 3 :"   );
         scanf ( "%d", &nPosition                           );

         if( nPosition == 1 || nPosition == 2 )
         {
            LinkedList_RemoveNode( &pHead, &pTail, nTemp, nPosition );
         }
         else if( nPosition == 3 )
         {
            printf( "   Enter a remove Data : " );
            scanf ( "%d", &nTemp                );
            LinkedList_RemoveNode( &pHead, &pTail, nTemp, nPosition );
         }
         else
         {
            printf( "   Error Input Number!!\n" );
         }
         PAUSE;
      }
      // All node Remove
      else if( nSelect == 5 )
      {
         CLS;
         printf( "\n   ______________________________\n" );
         printf( "      Remove All Linked List TEST\n"   );
         printf( "   ______________________________\n"   );

         LinkedList_RemoveAllNode( &pHead );

         printf( "   Remove All SUCCESS!!\n"             );
         PAUSE;
      }
      // Display LinkedList node
      else if( nSelect == 6 )
      {
         CLS;
         printf( "\n   ______________________________\n" );
         printf( "      Display Linked List TEST\n"      );
         printf( "   ______________________________\n"   );

         LinkedList_DisplayNode( pHead, ALL );
         PAUSE;
      }
      // Binary Tree compose and then Dispaly (Inorder)
      else if( nSelect == 7 )
      {
         CLS;
         printf( "\n   ______________________________\n" );
         printf( "      Sort Linked List TEST\n"         );
         printf( "   ______________________________\n"   );
         
         // Binary Tree Main
         BinaryTree_Main( &pTree, pHead );
         
         // Binary Tree Copy and then Display (Inorder)
         BinaryTree_Inorder( pTree );
         PAUSE;
         
         // Binary Remove all
         BinaryTree_RemoveAll( &pTree );
      }
      // Error input number
      else
      {
         CLS;
         printf( "\n   ______________________________\n" );
         printf( "   Error input Number!!\n"             );
         printf( "   ______________________________\n"   );
         PAUSE;
      }
   }
   return;
}
 
//===========================================================================
// DESCRIPTION
//    LinkedList_DisplayNode
//
// PARAMETERS
//    *pHead   : Head Node
//    nCase    : All and One node - Display method SELECT
//===========================================================================
void LinkedList_DisplayNode( Node *pHead, int nCase )
{
   switch( nCase )
   {
      // All node Display
      case  0:
         while( pHead != NULL )
         {
            printf( "\n   ______________________________\n"       );
            printf( "   LinkedList Data : %d\n", pHead->m_nData   );
            printf( "   LinkedList Next : 0x%x\n", pHead->m_pNext );
            printf( "   LinkedList Prev : 0x%x\n", pHead->m_pPrev );

            pHead = pHead->m_pNext;
         }
         printf( "   ______________________________\n" );
         break;

      // One node Display
      case  1:
         printf( "\n   ______________________________\n"       );
         printf( "   LinkedList Data : %d\n", pHead->m_nData   );
         printf( "   LinkedList Next : 0x%x\n", pHead->m_pNext );
         printf( "   LinkedList Prev : 0x%x\n", pHead->m_pPrev );
         printf( "   ______________________________\n"         );
         break;
   }
}
 
//===========================================================================
// DESCRIPTION
//    LinkedList_AddNode
//
// PARAMETERS
//    **ppHead    : Head node
//    **ppTail    : Tail node
//    nData       : Input Data
//    nPosition   : Input Position
//===========================================================================
void LinkedList_AddNode( Node **ppHead, Node **ppTail, int nData, int nPosition )
{
   // New node________________________
   Node *pTemp = NULL;

   MALLOC( pTemp );

   pTemp->m_nData = nData;
   pTemp->m_pNext = NULL;
   pTemp->m_pPrev = NULL;
   //_________________________________

   // in case : no Node -> New Head
   if( *ppHead == NULL )
   {
      *ppHead = pTemp;
      *ppTail = pTemp;

      LinkedList_DisplayNode( *ppHead, ONE );
   }
   // in case : Node existence
   else
   {
      // First Add - New Head
      if( nPosition == FIRST )
      {
         if( *ppHead )
         {
            (*ppHead)->m_pPrev   = pTemp;
            pTemp->m_pNext       = (*ppHead);
            (*ppHead)            = pTemp;
         }
         LinkedList_DisplayNode( *ppHead, ONE );
      }
      // Last Add - New Tail
      else if( nPosition == LAST )
      {
         if( *ppTail )
         {
            (*ppTail)->m_pNext   = pTemp;
            pTemp->m_pPrev       = (*ppTail);
            (*ppTail)            = pTemp;
         }
         LinkedList_DisplayNode( *ppTail, ONE );
      }
      // Error Input Number
      else
      {
         printf( "   Error Input Number!!\n" );
      }
   }
 }
 
//===========================================================================
// DESCRIPTION
//    LinkedList_InsertNode
//
// PARAMETERS
//    **ppHead    : Head node
//    **ppTail    : Tail node
//    nData       : Input Data
//    nTarget     : Traget Data
//===========================================================================
void LinkedList_InsertNode (Node **ppHead, Node **ppTail, int nData, int nTarget)
{
   Node  *pNode  = NULL;         // Insert Node
   Node  *pTemp  = NULL;         // Temporary space
   Node  *pList  = NULL;         // Head Node

   // New node________________________
   MALLOC( pNode );

   pNode->m_nData = nData;
   pNode->m_pPrev = NULL;
   pNode->m_pNext = NULL;
   //_________________________________

   pList = *ppHead;

   // no Head node >> New Head node
   if( pList == NULL )
   {
      *ppHead = pNode;
   }
   // Head node existence
   else
   {
      // Search Traget node
      while( pList )
      {
         if( pList->m_nData == nTarget )
         {
            break;
         }
         pList = pList->m_pNext;
      }

      // pList next to pNode
      if( pList )
      {
         pTemp          = pList->m_pNext;
         pList->m_pNext = pNode;
         pNode->m_pNext = pTemp;
         pNode->m_pPrev = pList;
         if( pTemp )
         {
            pTemp->m_pPrev = pNode;
         }
      }
      // In case : Target node is not existence
      else
      {
         printf( "\n   Error Input Node!!" );
         printf( "\n   It is not existence!!\n" );
         return;
      }

      // In case : pNode == Tail
      if( pNode->m_pPrev == *ppTail )
      {
         *ppTail = pNode;
      }
   }
   LinkedList_DisplayNode( pNode, ONE );
}
 
//===========================================================================
// DESCRIPTION
//    LinkedList_RemoveNode
//
// PARAMETERS
//    **ppHead    : Head node
//    **ppTail    : Tail node
//    nData       : Remove Data
//    nPosition   : Node position
//===========================================================================
void LinkedList_RemoveNode( Node **ppHead, Node **ppTail, int nData, int nPosition )
{
   Node *pTemp = NULL;           // Temporary space

   // In case : Remove node is Head node
   if ( nPosition == FIRST )
   {
      if( *ppHead == *ppTail )
      {
         RELEASEIF( *ppHead );
         *ppTail = NULL;
      }
      else
      {
         if( !*ppTail )
         {
            return;
         }
         if( *ppHead == NULL )
         {
            return;
         }
         pTemp          = (*ppHead)->m_pNext;
         pTemp->m_pPrev = NULL;
         *ppHead        = pTemp;
      }
      printf( "\n   Remove SUCCESS!!\n" );
   }
   // In case : Remove node is Tail node
   else if( nPosition == LAST )
   {
      if( *ppHead == *ppTail )
      {
         RELEASEIF( *ppHead );
         *ppTail = NULL;
      }
      else
      {
         pTemp = *ppHead;

         pTemp          = (*ppTail)->m_pPrev;
         pTemp->m_pNext = NULL;

         RELEASEIF( *ppTail );

         *ppTail = pTemp;
      }

      printf( "\n   Remove SUCCESS!!\n" );
   }
   // In case : Remove node is Target node
   else if( nPosition == SELECT )
   {
      Node *pPrev = NULL; // Previous Node
      Node *pNext = NULL; // Next Node

      pTemp = *ppHead;

      //Search Node
      while( pTemp != NULL && (pTemp->m_nData != nData) )
      {
         pTemp = pTemp->m_pNext;
      }

      if( pTemp != NULL )
      {
         pPrev = pTemp->m_pPrev;
         pNext = pTemp->m_pNext;

         if( pPrev )
         {
            pPrev->m_pNext = pNext;
         }
         else
         {
            *ppHead = pNext;
         }

         if( pNext )
         {
            pNext->m_pPrev = pPrev;
         }
         else
         {
            *ppTail = pPrev;
         }
         
         RELEASEIF( pTemp );
         printf( "\n   Remove SUCCESS!!\n" );
      }
   }
   else
   {
      printf( "   Error Input Number!!\n" );
   }
}
 
//===========================================================================
// DESCRIPTION
//    LinkedList_RemoveAllNode
//
// PARAMETERS
//    **ppHead    : Head node
//===========================================================================
void LinkedList_RemoveAllNode( Node **ppHead )
{
   Node *pRemove = NULL; // Delete Node

   while( *ppHead != NULL )
   {
      pRemove = *ppHead;
      *ppHead = (*ppHead)->m_pNext;

      RELEASEIF( pRemove );
   }

   (*ppHead) = NULL;
}
 
//===========================================================================
// DESCRIPTION
//    LinkedList_SearchNode
//
// PARAMETERS
//    **ppHead    : Head node
//    **ppTail    : Tail node
//    nData       : Search Data
//    nSearch     : Search direction
//===========================================================================
void LinkedList_SearchNode( Node *pHead, Node *pTail, int nData, int nSearch )
{
   Node *pTemp = NULL; //Print distinction

   // In case : Search direction is FORWARD
   if( nSearch == FORWARD )
   {
      pTemp = pHead;

      while( pTemp != NULL && (pTemp->m_nData != nData) )
      {
         pTemp = pTemp->m_pNext;
      }
   }
   // In case : Search direction is REVERSE
   else if( nSearch == REVERSE )
   {
      pTemp = pTail;
      while( pTemp != NULL && (pTemp->m_nData != nData) )
      {
         pTemp = pTemp->m_pPrev;
      }
   }
   // In case : Other number
   else
   {
      printf( "   Error Input Number!!\n" );
   }

   // In case : Find SUCCESS
   if( pTemp != NULL )
   {
      printf( "\n   Find SUCCESS!!\n" );
      LinkedList_DisplayNode( pTemp, ONE );
   }
   // In case : Not find SUCCESS
   else
   {
   printf( "\n   Not Find!!\n" );
   }
}
 
//===========================================================================
// DESCRIPTION
//    BinaryTree_Inorder
//
// PARAMETERS
//    *pTree      : Tree root node
//===========================================================================
void BinaryTree_Inorder( Tree *pTree )
{
   if( pTree )
   {
      if( pTree->m_pLeft )
      {
         BinaryTree_Inorder( pTree->m_pLeft );
      }
     
      printf( "\n   ______________________________\n"     );
      printf( "   LinkedList Data : %d\n", pTree->m_nData );
      printf( "   ______________________________\n"       );

      if( pTree->m_pRight )
      {
         BinaryTree_Inorder( pTree->m_pRight );
      }
   }
}
 
//===========================================================================
// DESCRIPTION
//    BinaryTree_Main
//
// PARAMETERS
//    **ppTree    : Tree node
//    *pList      : Head node
//===========================================================================
void BinaryTree_Main( Tree **ppTree, Node *pList )
{
   Tree *pLeaf = NULL; // New node

   if( pList == NULL ) return;

   while( pList )
   {
      // Create Node
      BinaryTree_CreateLeaf( &pLeaf, pList->m_nData );

      // In case : no Root node
      if( *ppTree == NULL )
      {
         *ppTree = pLeaf;
      }
      // In case : Root node existence
      else
      {
         BinaryTree_Insert( *ppTree, pLeaf );
      }

      // Move Node to next node
      pList = pList->m_pNext;
   }
}
 
//===========================================================================
// DESCRIPTION
//    BinaryTree_CreateLeaf
//
// PARAMETERS
//    **ppTree    : Tree node
//    nData       : Node data by Double Linked List
//===========================================================================
int BinaryTree_CreateLeaf( Tree **ppLeaf, int nData )
{
   *ppLeaf = (Tree *)malloc( sizeof(Tree) );

   if( *ppLeaf == NULL )
   {
      return FALSE;
   }

   (*ppLeaf)->m_nData   = nData;
   (*ppLeaf)->m_pRight  = NULL;
   (*ppLeaf)->m_pLeft   = NULL;

   return TRUE;
}
 
//===========================================================================
// DESCRIPTION
//    BinaryTree_Insert
//
// PARAMETERS
//    **ppTree    : Binary Tree
//    *pNewLeaf   : New node
//===========================================================================
void BinaryTree_Insert( Tree *pTree, Tree *pNewLeaf )
{
   // Insert - Left Node
   if( pTree->m_nData > pNewLeaf->m_nData )
   {
      if( pTree->m_pLeft )
      {
         BinaryTree_Insert( pTree->m_pLeft, pNewLeaf );
      }
      else
      {
         pTree->m_pLeft = pNewLeaf;
      }
   }
   // Insert - Right Node or Equal
   else if( pTree->m_nData < pNewLeaf->m_nData ||
            pTree->m_nData == pNewLeaf->m_nData     )
   {
      if( pTree->m_pRight )
      {
         BinaryTree_Insert( pTree->m_pRight, pNewLeaf );
      }
      else
      {
         pTree->m_pRight = pNewLeaf;
      }
   }
}
 
//===========================================================================
// DESCRIPTION
//    BinaryTree_RemoveAll
//
// PARAMETERS
//    **ppTree    : Binary Trees
//===========================================================================
void BinaryTree_RemoveAll( Tree **ppTree )
{
   if( (*ppTree) )
   {
      // Remove - Left node
      if( (*ppTree)->m_pLeft )
      {
         BinaryTree_RemoveAll( &(*ppTree)->m_pLeft  );
      }

      // Remove - Right node
      if( (*ppTree)->m_pRight )
      {
         BinaryTree_RemoveAll( &(*ppTree)->m_pRight );
      }
      RELEASEIF( (*ppTree) );
   }

   (*ppTree) = NULL;
}

#endif //_LINKEDLIST_BINARYSEARCHTREE_