void CBTInsert(BTNode *tree, BTNode *new


void CBTInsert(BTNode *tree, BTNode *new_node)
{
    int llcnt(0),lrcnt(0),rrcnt(0);
    BTNode *lch,*rch,*p,*lb;
    if(tree-lchild==NULL)//insert
        tree-lchild=new_node;
    else if(tree-rchild==NULL)//insert
        tree-rchild=new_node;
    else
    {
        p=tree-lchild;
        while(p-lchild){
            llcnt++;
            p=p-lchild;
        }
        lb=p;//remember the left tree's left bottom;
        p=tree-lchild;
        while(p-rchild){
            lrcnt++;
            p=p-rchild;
        }

        if(lrcnt  llcnt)
            CBTInsert(tree-lchild,new_node);
        else{//lrcnt==llcnt
            //first,compute rrcnt
            p=tree-rchild;
            while(p-rchild){
                rrcnt++;
                p=p-rchild;
            }
            if(rrcnt==lrcnt)            //insert, because it's a full CBT
                lb-lchild=new_node;
            else //rrcntlrcnt
//first,compute rrcnt
            p=tree-rchild;
            while(p-rchild){
                rrcnt++;
                p=p-rchild;
            }
            if(rrcnt==lrcnt)            //insert, because it's a full CBT
                lb-lchild=new_node;
            else //rrcntlrcnt
                CBTInsert(tree-rchild,new_node);
        }
    }
}




最新回复(0)
/jishuM3p8E53Xkrnsr8GqkaIaR0Kk7FGxW6JTJNPSQ4O9bEQ_3D4794901
8 简首页