二叉排序树怎么构造_建立二叉排序树_怎么画二叉排序树(2)

//从二叉树中删除任意结点，其关键字为x
int DeleteBT(BiTree *BT,int key)
{
    if(!*BT) return 0;//不存在关键字等于key的数据元素
    else
    {
        if(key==(*BT)->data) 
          return Delete(BT);
        else if(key<(*BT)->data) 
          return DeleteBT(&(*BT)->lchild,key);
        else             
          return DeleteBT(&(*BT)->rchild,key);
    }
}

//删除结点
int Delete(BiTree *p)
{
    BiTree q,s;
    if((*p)->rchild==NULL)    //没有右孩子
    {
        q=*p;  *p=(*p)->lchild;  free(q);
    }
    else if((*p)->lchild==NULL)  //没有左孩子
    {
        q=*p;  *p=(*p)->rchild;  free(q);
    }
    else      //左右子树均不为空
    {
        q=*p; s=(*p)->lchild;
        while(s->rchild)
        {
            q=s;  s=s->rchild;
        }
        (*p)->data=s->data; 
            //s指向被删除结点的直接前驱
        if(q!=*p)
            q->rchild=s->lchild;  //重建q的右子树
        else 
            q->lchild=s->lchild;  //重建q的左子树
        free(s);
    }
    return 1;
}

//以树的形式输出二叉排序树
void Paint(BiTree BT,int x,int y,int g)
{
    char c[3];
    int right = 0, left = 0;
    if (BT)
    {
        setcolor(WHITE);
        circle(x, y, 10);
        Sleep(ms);          
        //将相应数字转化为字符
        c[0] = BT->data / 10 + 48;
        c[1] = BT->data % 10 + 48;
        c[2] = '\0';
        outtextxy(x-7, y-6, c);
        Sleep(ms);
        if (BT->lchild != NULL)
        {
            if (x>g) left = (x - g) / 2 + g;
            if (x<g) left = (x - g) / 2 + x;
            line(x - 3, y, left, y + 50);
            Sleep(ms);
        }
        if (BT->rchild != NULL)
        {
            if(BT->lchild!=NULL)right=2*x-left;
            else    
            {
                if(x<g) right =(x+g)/2;     
                else right=x+40;
            }
            line(x + 3, y, right, y + 50);
            Sleep(ms);
        }
        Paint(BT->lchild, left, y + 50, x);
        Paint(BT->rchild, right, y + 50, x);
    }
}
//前序遍历二叉树
void prorder(BiTree &BT)
{
    if (BT!= NULL)
    {
        printf("%3d ", BT->data);  //访问结点
        prorder(BT->lchild);
        prorder(BT->rchild);
    }
}

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-32053-2.html