//二叉排序树
//BST-插入
bool BST_Insert(BiTree *Tree,int Num)
{
    if ((*Tree)==NULL)
    {
        (*Tree) = (BiTree)malloc(sizeof(BiNode));
        (*Tree)->data = Num;
        (*Tree)->lchild = (*Tree)->rchild = NULL;
        return true;
    }
    else if(Num<((*Tree)->data))
    {
        return BST_Insert(&((*Tree)->lchild),Num);
    }
    else if (Num>((*Tree)->data))
    {
        return BST_Insert(&((*Tree)->rchild),Num);
    }
    else
    {
        return false;
    }
}

//BST-建立
bool BST_Bulid(BiTree *Tree,ElemType Buff[],int len)
{
    int ErrorCnt=0;

    for (int i=0;i<len;i++)
    {
        if (!BST_Insert(Tree,Buff[i]))
        {
            ErrorCnt++;
        }
    }

    if (ErrorCnt>0)
    {
        return false;
    } 
    else
    {
        return true;
    }
}

//递归查找
BiTree BST_Search1(BiTree Tree,ElemType num)
{
    if (Tree==NULL)
    {
        return NULL;
    }

    if (Tree->data<num)
    {
        return BST_Search1(Tree->rchild,num);
    }
    else if(Tree->data>num)
    {
        return BST_Search1(Tree->lchild,num);
    }
    else
    {
        return Tree;
    }
}

//迭代查找
BiTree BST_Search2(BiTree Tree,ElemType num)
{
    while(Tree!=NULL)
    {
        if (num==(Tree->data))
        {
            return Tree;
        }
        else if (num<(Tree->data))
        {
            Tree=Tree->lchild;
        } 
        else
        {
            Tree=Tree->rchild;
        }
    }

    return NULL;
}

//删除某个元素
//左或右子树为空，直接用左子树或右子树的值代替；
//否则，找到右子树中中序遍历的第一个元素代替上去。
//中序遍历第一个元素是最左边的元素
bool BST_Delete(BiTree Tree,ElemType num)
{
    ElemType Temp;
    BiTree DeleteNode = BST_Search1(Tree,num);
    if (DeleteNode!=NULL)
    {
        if (DeleteNode->lchild==NULL)
        {
            BiTree Temp;

            DeleteNode->data = DeleteNode->rchild->data;
            Temp = DeleteNode->lchild;
            //注意下面这两行顺序不能颠倒
            DeleteNode->lchild = DeleteNode->rchild->lchild;
            DeleteNode->rchild = DeleteNode->rchild->rchild;
            DeleteNode = Temp;
        }
        else if(DeleteNode->rchild==NULL)
        {
            BiTree Temp;

            DeleteNode->data = DeleteNode->lchild->data;
            Temp = DeleteNode->lchild;
            //注意下面这两行顺序不能颠倒
            DeleteNode->rchild = DeleteNode->lchild->rchild;
            DeleteNode->lchild = DeleteNode->lchild->lchild;
            DeleteNode = Temp;
        }
        else
        {
            BiTree MidOrderFirstElem = DeleteNode;
            if (MidOrderFirstElem->rchild->lchild!=NULL)
            {
                MidOrderFirstElem = MidOrderFirstElem->rchild;
                while(MidOrderFirstElem->lchild->lchild!=NULL)
                {
                    MidOrderFirstElem = MidOrderFirstElem->lchild;
                }

                DeleteNode->data = MidOrderFirstElem->lchild->data;
                DeleteNode = MidOrderFirstElem->lchild;
                MidOrderFirstElem->lchild = DeleteNode->rchild;
            }
            else
            {
                MidOrderFirstElem->data = MidOrderFirstElem->rchild->data;
                DeleteNode = MidOrderFirstElem->rchild;
                MidOrderFirstElem->rchild = MidOrderFirstElem->rchild->rchild;
            }
        }
        free(DeleteNode);

        return true;
    }
    else
    {
        return false;
    }
}