dosavl.cpp

这是一个数据结构的小程序

                 q = q->RChild;
             if (q->RChild == NULL)
             {
         		 
                 q->RChild = Curr;
        		 Curr = Curr->LChild;
             }
             else
             { 
				 cout << Curr->Data<<' ';
                 Curr = Curr->RChild;
                 q->RChild = NULL;
             }
             
         }
     }
 }


 template<typename Type>
 int AvlTree<Type>::GetMin(Type& it)
 {
     pNode   Curr = head->LChild;
     if (!Curr) return 0;
     while (Curr->LChild) Curr = Curr->LChild;
     it = Curr->Data;
     return 1;
 }   

 template<typename Type>
int  AvlTree<Type>::GetMax(Type& it)
 {
     pNode   Curr = head->LChild;
     if (!Curr) return 0;
     while (Curr->RChild) Curr = Curr->RChild;
     it = Curr->Data;
     return 1;
 }  

//L

template<typename Type>
inline void AvlTree<Type>::ChangeChild(pNode Parent, pNode OldChild, pNode NewChild)
{
    if(Parent->LChild == OldChild)
	Parent -> LChild = NewChild;
    else
	Parent -> RChild = NewChild;
}

template<typename Type>
inline void AvlTree<Type>::LChangeBalanceI(pNode TheSelect)
{
    TheSelect -> BalanceFactor = 0;
    TheSelect -> LChild -> BalanceFactor = 0;
}

template<typename Type>
inline void AvlTree<Type>::LChangeBalanceD(pNode TheSelect)
{
    pNode A = TheSelect;
    pNode B = TheSelect->LChild;
    if(B->BalanceFactor == 0)
    {
	A->BalanceFactor = 1;
	B->BalanceFactor = -1;
    }
    else
    {
	A->BalanceFactor = 0;
	B->BalanceFactor = 0;
    }
}

template<typename Type>
inline typename AvlTree<Type>::pNode AvlTree<Type>::LRotate(pNode TheSelect)
{
     pNode A = TheSelect;
     pNode B = TheSelect -> LChild;
     A -> LChild = B -> RChild;
     B -> RChild = A;
     return B;
}


 // LR
 template<typename Type>
 inline void AvlTree<Type>::LRChangeBalanceI(pNode TheSelect)
 {
     pNode A = TheSelect;
     pNode B = TheSelect->LChild;
     pNode C = B->RChild;
     
     switch (C->BalanceFactor)
     {
     case  1:
                 B->BalanceFactor = 0;
                 A->BalanceFactor = -1;
                 C->BalanceFactor = 0;
                 break;
     case -1:
                 B->BalanceFactor = 1;
                 A->BalanceFactor = 0;
                 C->BalanceFactor = 0;
                 break;
     case 0:
                 B->BalanceFactor = 0;
                 A->BalanceFactor = 0;
                 C->BalanceFactor = 0;
     }
 }

 template<typename Type>
 inline void AvlTree<Type>::LRChangeBalanceD(pNode TheSelect)
 {
     pNode A = TheSelect;
     pNode B = TheSelect->LChild;
     pNode C = B->RChild;
     
     switch (C->BalanceFactor)
     {
     case  -1:
                 A->BalanceFactor = 0;
                 B->BalanceFactor = 1;
                 C->BalanceFactor = 0;
                 break;
     case 0:
                 A->BalanceFactor = 0;
                 B->BalanceFactor = 0;
                 C->BalanceFactor = 0;
                 break;
     case 1:
                 A->BalanceFactor = -1;
                 B->BalanceFactor = 0;
                 C->BalanceFactor = 0;
     }
 }

 template<typename Type>
 inline typename AvlTree<Type>::pNode AvlTree<Type>::LRRotate(pNode TheSelect)
 {
     pNode A = TheSelect;
     pNode B = TheSelect->LChild;
     pNode C = B->RChild;
     
     B->RChild = C->LChild;
     A->LChild = C->RChild;
     C->LChild = B;
     C->RChild = A;
                 
     return C;
 }

 // R
 template<typename Type>
 inline void AvlTree<Type>::RChangeBalanceI(pNode TheSelect)
 {
     TheSelect->BalanceFactor = 0;
     TheSelect->RChild->BalanceFactor = 0;
 }

 template<typename Type>
 inline void AvlTree<Type>::RChangeBalanceD(pNode TheSelect)
 {
     pNode A = TheSelect;
     pNode B = TheSelect->RChild;
     if (B->BalanceFactor == 0)
     {
         A->BalanceFactor = -1;
         B->BalanceFactor = 1;
     }
     else
     {
         A->BalanceFactor = 0;
         B->BalanceFactor = 0;
     }
 }

 template<typename Type>
 inline typename AvlTree<Type>::pNode AvlTree<Type>::RRotate(pNode TheSelect)
 {
     pNode A = TheSelect;
     pNode B = TheSelect->RChild;
     
     A->RChild = B->LChild;
     B->LChild = A;
     
     return B;
 }

 // RL
 template<typename Type>
 inline void AvlTree<Type>::RLChangeBalanceI(pNode TheSelect)
 {
     pNode A = TheSelect;
     pNode B = TheSelect->RChild;
     pNode C = B->LChild;
     
     switch (C->BalanceFactor)
     {
     case  1:
             B->BalanceFactor = -1;
             A->BalanceFactor = 0;
             C->BalanceFactor = 0;
             break;
     case -1:
             B->BalanceFactor = 0;
             A->BalanceFactor = 1;
             C->BalanceFactor = 0;
             break;
     case 0:
             B->BalanceFactor = 0;
             A->BalanceFactor = 0;
             C->BalanceFactor = 0;
     }
 }

 template<typename Type>
 inline void AvlTree<Type>::RLChangeBalanceD(pNode TheSelect)
 {
     
     pNode A = TheSelect;
     pNode B = TheSelect->RChild;
     pNode C = B->LChild;
     
     switch (C->BalanceFactor)
     {
     case  -1:
                 A->BalanceFactor = 1;
                 B->BalanceFactor = 0;
                 C->BalanceFactor = 0;
                 break;
     case 0:
                 A->BalanceFactor = 0;
                 B->BalanceFactor = 0;
                 C->BalanceFactor = 0;
                 break;
     case 1:
                 A->BalanceFactor = 0;
                 B->BalanceFactor = -1;
                 C->BalanceFactor = 0;
     }
 }

 template<typename Type>
 inline typename AvlTree<Type>::pNode AvlTree<Type>::RLRotate(pNode TheSelect)
 {
     pNode A = TheSelect;
     pNode B = TheSelect->RChild;
     pNode C = B->LChild;
             
     B->LChild = C->RChild;
     A->RChild = C->LChild;
     C->LChild = A;
     C->RChild = B;
             
     return C;
 }

 template<typename Type>
 void    AvlTree<Type>::CleanAll()
 {
     if (head) CleanAll(head->LChild);
     head = NULL;
 }    

 template<typename Type> void AvlTree<Type>::CleanAll(pNode head)
 {
     if (!head) return;
     CleanAll(head->LChild);
     CleanAll(head->RChild);
     delete head;
 }

	

 int main()
 {
     AvlTree<int> it,itt;
	 int m;

	 for (int i = 1; i < 10; ++i)
         itt.Insert(i);
	 itt.InOrder();
	 
	 itt.GetMax(m);
	 cout <<endl << m << endl;
	 itt.GetMin(m);
	 cout << m << endl;
     


	 DWORD dwStart = GetTickCount();
     for (i = 1; i < 10000000; ++i)
         it.Insert(i);
	 cout<<(GetTickCount() - dwStart)/1000.0 <<endl;

    	 dwStart = GetTickCount();
     for (i = 1; i < 10000000; ++i)
	 it.Delete(i);
     cout<<(GetTickCount() - dwStart)/1000.0 <<endl;
	 system("pause");

   return 0;
 }