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

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

#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编辑过]

哇~很简单的AVL树呀~打算下一个目标是看看红黑树~看来实现这短期目标可能性不太大~还是先弄弄删除节点的操作吧~

这种方法效率插入较低~我第一次发AVL树那代码求高度方法类似这样~每次插入都要要遍历高度这样会严重影响效率~虽然我第二次发的高度那里有点偏差~但是求高度的时间可以理解为o(1)~

找到原因了~看看是不是这样~还是AVL树旋转理解不太透彻~singlerotatewithleft对doulberotatewithright这里匹配出问题了~另一半旋转也是这样~

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


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

扑通

刚刚调试过了~改了旋转那那里还是这样~还要再认真看看才行~

W版主如此大礼，小弟怎么承受的起？

我反复看了几次旋转，应该不是那里的问题。

感觉要大改才行~迭代遍历这样会出问题的~

因为逻辑顺序出问题了~
是先插入节点然后在回溯的时候调节平衡~

你这个是先调节平衡再插入节点这样会出问题的~

你下一次插入的数据和上一次插入的数据不一定相等~怎么会拿下一次插入的数据来对上一次的平衡作为比较？~~

不用递归的话还是乖乖地用栈来实现吧~

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