POJ 2418 Hardwood Species( AVL-Tree )-白红宇

POJ 2418 Hardwood Species( AVL-Tree )

阅读量：5318 次

发布时间：2019-06-14

本文共 3213 字，大约阅读时间需要 10 分钟。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         typedef struct AVLTree{    char name[31];    int nCount;    int nHeight;    struct AVLTree* pLeft;    struct AVLTree* pRight;}AVLTree;int Max( int a, int b );int Height( AVLTree* pNode );AVLTree* Insert( char* s, AVLTree* pNode );AVLTree* LLRotate( AVLTree* pNode );AVLTree* RRRotate( AVLTree* pNode );AVLTree* LRRotate( AVLTree* pNode );AVLTree* RLRotate( AVLTree* pNode );void PrintTree( AVLTree* pNode );int n = 0;int main(){    char s[31];    AVLTree* pRoot = NULL;    while( gets( s ) != NULL ){        pRoot = Insert( s, pRoot );        n++;    }    PrintTree( pRoot );    return 0;}int Max( int a, int b ){    return ( a > b ) ? a : b;}int Height( AVLTree* pNode ){    if( pNode == NULL )        return -1;    return pNode->nHeight;}AVLTree* Insert( char* s, AVLTree* pNode ){    if( pNode == NULL ){        pNode          = ( AVLTree* ) malloc( sizeof( AVLTree ) );        strcpy( pNode->name, s );        pNode->nCount  = 1;        pNode->nHeight = 0;        pNode->pLeft   = NULL;        pNode->pRight  = NULL;    }    else if( strcmp( s, pNode->name ) == 0 ){        pNode->nCount++;    }    else if( strcmp( s, pNode->name ) < 0 ){        pNode->pLeft = Insert( s, pNode->pLeft );        if( Height( pNode->pLeft ) - Height( pNode->pRight ) == 2 ){            if( strcmp( s, pNode->pLeft->name ) < 0 ){                pNode = LLRotate( pNode );            }            else{                pNode = LRRotate( pNode );            }        }    }    else if( strcmp( s, pNode->name ) > 0 ){        pNode->pRight = Insert( s, pNode->pRight );        if( Height( pNode->pRight ) - Height( pNode->pLeft ) == 2 ){            if( strcmp( s, pNode->pRight->name ) > 0 ){                pNode = RRRotate( pNode );            }            else{                pNode = RLRotate( pNode );            }        }    }    pNode->nHeight = Max( Height( pNode->pLeft ), Height( pNode->pRight ) ) + 1;    return pNode;}AVLTree* LLRotate( AVLTree* pNode ){    AVLTree* pNodeLeft = pNode->pLeft;    pNode->pLeft       = pNodeLeft->pRight;    pNodeLeft->pRight  = pNode;    pNode->nHeight     = Max( Height( pNode->pLeft ),     Height( pNode->pRight ) ) + 1;    pNodeLeft->nHeight = Max( Height( pNodeLeft->pLeft ), pNode->nHeight ) + 1;    return pNodeLeft;}AVLTree* RRRotate( AVLTree* pNode ){    AVLTree* pNodeRight = pNode->pRight;    pNode->pRight       = pNodeRight->pLeft;    pNodeRight->pLeft   = pNode;    pNode->nHeight      = Max( Height( pNode->pLeft ),       Height( pNode->pRight ) ) + 1;    pNodeRight->nHeight = Max( Height( pNodeRight->pRight ), pNode->nHeight ) + 1;    return pNodeRight;}AVLTree* LRRotate( AVLTree* pNode ){    pNode->pLeft = RRRotate( pNode->pLeft );    return LLRotate( pNode );}AVLTree* RLRotate( AVLTree* pNode ){    pNode->pRight = LLRotate( pNode->pRight );    return RRRotate( pNode );}void PrintTree( AVLTree* pRoot ){    if( pRoot == NULL )        return;    PrintTree( pRoot->pLeft );    printf( "%s %.4f\n", pRoot->name, ( ( double )( pRoot->nCount ) / ( double )n ) * 100 );    PrintTree( pRoot->pRight );}