균형 이 진 트 리 의 실현

//      
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

typedef int ElementType; 

typedef struct BinaryNode
{
    ElementType data;
    int height;
    unsigned int freq; //              
    struct BinaryNode *left,*right;
}BinaryNode,*BinaryTree;

//    
int Height(BinaryTree pNode)
{
    return pNode == NULL ? -1 : pNode->height;
}

int Max(int a, int b)
{
    return a < b ? b : a;
}

//LL   
void RotateWithLeft(BinaryTree &pNode)
{ 
    BinaryTree pTemp = pNode->left; //         
    pNode->left = pTemp->right;
    pTemp->right = pNode;
     //       ，      , pNode，pTemp             ； 
    pNode->height = Max(Height(pNode->left), Height(pNode->right)) + 1;
    pTemp->height = Max(Height(pTemp->left), Height(pTemp->right)) + 1;
     //pTemp     ，     ，      ，         ，             ；
    pNode = pTemp;
}
//RR  
void RotateWithRight(BinaryTree &pNode)
{
    BinaryTree pTemp = pNode->right; //        
    pNode->right = pTemp->left;
    pTemp->left = pNode;
     //       ，      , pNode，pTemp             ； 
    pNode->height = Max(Height(pNode->left), Height(pNode->right)) + 1;
    pTemp->height = Max(Height(pTemp->left), Height(pTemp->right)) + 1;
     //pTemp     ，     ，      ，         ，             ； 
    pNode = pTemp;
}

//LR  
void DoubleRotateWithLeft(BinaryTree &pNode)
{

    RotateWithRight(pNode->left);
    RotateWithLeft(pNode);
} 

//RL  
void DoubleRotateWithRight(BinaryTree &pNode)
{

    RotateWithLeft(pNode->right);
    RotateWithRight(pNode);
} 


//      
void LeftBalance(BinaryTree &pNode)
{
    BinaryTree pTemp = pNode->left;
    if(Height(pTemp->left) - Height(pTemp->right) == -1)
    {
         //        ，        
        DoubleRotateWithLeft(pNode);//LR 
    }
    else
    {
        RotateWithLeft(pNode);//LL  
    }
 } 

//      
void RightBalance(BinaryTree &pNode)
{
    BinaryTree pTemp = pNode->right;
    if(Height(pTemp->right) - Height(pTemp->left) == -1)
    {   //        ，         
        DoubleRotateWithRight(pNode); //RL  
    }
    else
    {
        RotateWithRight(pNode);  //RR  
    }
}

//   
void AVL_Insert(BinaryTree &pNode, ElementType key)
{
    if(NULL == pNode)
    {
        pNode = new BinaryNode;
        pNode->data = key;
        pNode->height = 0;
        pNode->freq= 1;
        pNode->left = NULL;
        pNode->right = NULL;    
    } 
    else if(key < pNode->data) //      
    {
        AVL_Insert(pNode->left, key);
        //      AVL     
        if((Height(pNode->left) - Height(pNode->right)) == 2)
        {
            LeftBalance(pNode);//       
        }
    }
    else if(key > pNode->data) //      
    {
        AVL_Insert(pNode->right, key);
        //      AVL     
        if((Height(pNode->right) - Height(pNode->left)) == 2)
        {
            RightBalance(pNode); //       
        }
    }
    else
    {
        pNode->freq++;
    }

    pNode->height = Max(Height(pNode->left), Height(pNode->right)) + 1; //      
}

//   
BinaryTree AVL_Search(BinaryTree &pNode, ElementType key)
{
    if(pNode == NULL)
    {
        return NULL;
    }
    else if(key > pNode->data) 
    {
        AVL_Search(pNode->right, key);
    }
    else if(key < pNode->data)
    {
        AVL_Search(pNode->left, key);
    }
    else
    {
        return pNode;
    }
}

//  
void AVL_Delete(BinaryTree &pNode, ElementType key) 
{
    if(pNode == NULL) //     
    {
        return ; 
    }
    if(key < pNode->data) //        
    {
        AVL_Delete(pNode->left, key);

        if((Height(pNode->right) - Height(pNode->left)) == 2) //         ，            
        {
            RightBalance(pNode);
        }   
    }
    else if(key > pNode->data)
    {
        AVL_Delete(pNode->right, key);

        if((Height(pNode->left) - Height(pNode->right)) == 2) //         ，            
        {
            LeftBalance(pNode); //       
        }   
    }
    else //          
    {
        if(pNode->left == NULL) //       
        {
            BinaryTree pTemp = pNode;
            pNode = pNode->right; //          
            free(pTemp);  //     
        }
        else if(pNode->right == NULL) //       
        {
            BinaryTree pTemp = pNode;
            pNode = pNode->left; //          
            free(pTemp);  //                
        }
        else //         
        {
            //                                 
            BinaryTree pTemp = pNode->left;
            while(pTemp->right != NULL)
            {
                pTemp = pTemp->right;
            }
            pNode->data = pTemp->data;
            AVL_Delete(pNode->left,pTemp->data);
        }
    }

    if(pNode)
    {
        pNode->height = Max(Height(pNode->left), Height(pNode->right));
    }
}

//    
void AVL_InorderPrint(BinaryTree &pRoot)
{
    if(pRoot != NULL)
    {
        AVL_InorderPrint(pRoot->left);
        cout << pRoot->data << " ";
        AVL_InorderPrint(pRoot->right);
    }   
} 

int main()
{
    BinaryTree root = NULL;
    AVL_Insert(root,3);
    AVL_Insert(root,2);  
    AVL_Insert(root,1);  
    AVL_Insert(root,4);  
    AVL_Insert(root,5);  
    AVL_Insert(root,6);  
    AVL_Insert(root,7);  
    AVL_Insert(root,16);  
    AVL_Insert(root,15);  
    AVL_Insert(root,14); 
    AVL_Insert(root,13);
    AVL_Insert(root,12);  
    AVL_Insert(root,11);  
    AVL_Insert(root,10); 
    AVL_Insert(root,8);
    AVL_Insert(root,9);

    AVL_InorderPrint(root);
    printf("
%d
",root->height);


    AVL_Delete(root,8);  
   // AVL_Delete(root,5);
    AVL_InorderPrint(root);

    BinaryTree k = AVL_Search(root,15);  
    if (k == NULL)  
    {  
        printf("     15
");  
    }  
    else  
    {  
        printf("       ：%d
",k->height);  
        if (NULL!=k->left)  
        {  
            printf("        ：%d
",k->left->data);  
        }  
        if (NULL!=k->right)  
        {  
            printf("        ：%d
",k->right->data);  
        }  

    }
    system("pause");
    return 0;
}