首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

AVL树的有关问题

2013-09-26 
AVL树的问题bool AvlTreeT::Insert(AvlNodeT * &sRoot,T x,bool &taller){//递归函数,从sRoot这棵树寻

AVL树的问题
bool AvlTree<T>::Insert(AvlNode<T> * &sRoot,T x,bool &taller)
{
    //递归函数,从sRoot这棵树寻找合适的位置,插入值为x的节点
    bool success;
    if ( sRoot == NULL )  //函数的出口,从叶节点插入
    {
        sRoot = new AvlNode<T>(x);
        success = sRoot != NULL ? true : false;
        if ( success ) taller = true;
    }
    else if ( x < sRoot->data )  //如果x的值小于sRoot的值
    {
        //Insert的递归调用,从sRoot的左子树寻找合适的位置插入
        success = Insert ( sRoot->left, x, taller );
        if ( taller ) //如果插入后使得sRoot的左高度增加
        {
            switch ( sRoot->balance )
            {
            case -1 :
                LeftBalanceAfterInsert( sRoot, taller );
                break;
            case 0 :
                sRoot->balance = -1;
                break;
            case 1 :
                sRoot->balance = 0;
                taller = false;
                break;
            }
        }
    }
    else if ( x > sRoot->data )  //如果x的值大于sRoot的值
    {
        //Insert的递归调用,从sRoot的右子树寻找合适的位置插入


        success = Insert ( sRoot->right, x, taller );

        if ( taller ) //如果插入后使得sRoot的右高度增加
        {
            switch ( sRoot->balance )
            {
            case -1 :
                sRoot->balance = 0;
                taller = false;
                break;
            case 0 :
                sRoot->balance = 1;
                break;
            case 1 :
                RightBalanceAfterInsert( sRoot, taller );
                break;
            }
        }
    }
    return success;
}

这个插入函数看不太懂,大家解释下,主要是,switch函数还有taller的值是干嘛的?
[解决办法]
你先把C语言的语法搞懂,再搞懂AVL树本身是怎么回事,再来研究这代码。

热点排行