AVL树（迭代版本） - C语言论坛

楼主

已结贴√ 问题点数：100 回复次数：20

AVL树（迭代版本）

这并不是高效的迭代版本，原来在于使用了绝对高度，而对高度函数的两次调用让迭代获得的些许速度优势荡然无存。

目前还没想到怎么处理高度，如果你有好的建议，请提出，不胜感谢。

程序代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define T AVLTREE
typedef struct T *T;

struct T {
    int Element;
    T Left;
    T Right;
};

void
Insert( T *RootPP, int X ); 

void
Print( T Root );



int
main( void )
{
    T Root;
    int ix,i;

    Root = NULL;
    srand( ( unsigned )time( NULL ) );


    for( ix = 0; 20 > ix; ++ix )
        i = rand() % 1000, fprintf( stderr,"待插入的值是 %d\n", i ), Insert( &Root, i );

    Print( Root );

    return 0;
}

void
Print( T Root )
{
    if( NULL == Root )
        return;


    Print( Root->Left );
    printf( "%5d ", Root->Element );
    Print( Root->Right );
}


int
Heigh( T Root );

T
SingleRotateWithLeft( T Node );
T
SingleRotateWithRight( T Node );
T
DoubleRotateWithLeft( T Node );
T
DoubleRotateWithRight( T Node );


void
Insert( T *RootPP, int X )
{
    T New;
    T Next;
    T *This;
    int L_Heigh, R_Heigh;

    This = RootPP;

    while( NULL != ( Next = *This ) ) 
    {
        if( X > Next->Element )

            This = &Next->Right;
        else if( X < Next->Element )

            This = &Next->Left;
        else
            return;
    }


    New = ( T )malloc( sizeof( struct T ) );
    if( NULL == New )
        exit( EXIT_FAILURE );
    New->Element = X;
    New->Left = NULL;
    New->Right = NULL;
    *This = New;
    printf( "\n\n" );


    while( NULL != *RootPP ) 
    {

        L_Heigh = Heigh( (*RootPP)->Left );
        R_Heigh = Heigh( (*RootPP)->Right);
        printf( "左子树高度 = %d, 右子树高度 = %d\n", L_Heigh, R_Heigh );

        if( X > (*RootPP)->Element )
        {
            if( 2 <= R_Heigh - L_Heigh )
            {
                if( X > (*RootPP)->Right->Element )
                    fprintf( stderr,"越界点：1\n" ), *RootPP = SingleRotateWithRight( *RootPP );
                else
                    fprintf( stderr,"越界点：2\n" ), *RootPP = DoubleRotateWithRight( *RootPP );
                continue;
            }

            RootPP = &(*RootPP)->Right;
        }
        else if( X < (*RootPP)->Element )
        {

            if( 2 <= L_Heigh - R_Heigh )
            {
                if(  X < (*RootPP)->Left->Element )
                    fprintf( stderr,"越界点：3\n" ), *RootPP = SingleRotateWithLeft( *RootPP );                                
                else
                    fprintf( stderr,"越界点：4\n" ), *RootPP = DoubleRotateWithLeft( *RootPP );
                continue;
            }

            RootPP = &(*RootPP)->Left;
        }
        else
            return;
    }



}    


int
Heigh( T Root )
{
    int u, v;

    if( NULL == Root )
        return -1;

    u = Heigh( Root->Left );
    v = Heigh( Root->Right );

    if( u > v )
        return u + 1;
    else
        return v + 1;
}


T
SingleRotateWithLeft( T Node )
{
    T Temp;

    Temp = Node->Left;
    Node->Left = Temp->Right;
    Temp->Right = Node;

    return Temp;
    
}


T
SingleRotateWithRight( T Node )
{
    T Temp;

    Temp = Node->Right;
    Node->Right = Temp->Left;
    Temp->Left = Node;

    return Temp;
}


T
DoubleRotateWithLeft( T Node )
{
/*    Node->Left = SingleRotateWithRight( Node->Left );
    return SingleRotateWithLeft( Node );
*/
    T K1, K2;

    K1 = Node->Left;
    K2 = K1->Right;

    K1->Right = K2->Left;
    Node->Left = K2->Right;
    K2->Left = K1;
    K2->Right = Node;

    return K2;
}


T
DoubleRotateWithRight( T K1 )
{
/*    Node->Right = SingleRotateWithLeft( Node->Right );
    return SingleRotateWithRight( Node ); 
*/

    T K2, K3;

    K3 = K1->Right;
    K2 = K3->Left;

    K1->Right = K2->Left;
    K3->Left = K2->Right;
    K2->Left = K1;
    K2->Right = K3;

    return K2;

    
}

[此贴子已经被作者于2017-6-12 18:10编辑过]

搜索更多相关主题的帖子: color　

第 2 楼

得分:0

回复 4楼九转星河

如果可以你修改一下旋转哪里，然后编译看看。我现在在上班，没办法修改调试。

另外高度问题，跌代版本比预料中的要复杂很多，这就是我一直没想到办法解决的问题。所以不得不求输的绝对高度。