学步园

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 //rrcnt<lrcnt
//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 //rrcnt<lrcnt
                CBTInsert(tree->rchild,new_node);
        }
    }
}