/*
二叉排序树的创建遍历及删除
输出结果：
中序遍历:1   2   4   5   6   7   9   10  14  15  17  18  19  20  25  30  35  40
层序遍历:20  14  25  5   15  35  4   10  17  30  40  2   6   19  1   9   18  7
Treeheight = 7
请输入待寻找的数字:5
找到了5.
请输入待寻找父节点的数字:5
5的父节点值为14
请输入要删除的节点值:5
删除后root = 20 proot = 00A8FA6C
中序遍历:1   2   4   6   7   9   10  14  15  17  18  19  20  25  30  35  40
层序遍历:20  14  25  4   15  35  2   10  17  30  40  1   6   19  9   18  7
请输入要删除的节点值:7
删除后root = 20 proot = 00A8FA6C
中序遍历:1   2   4   6   9   10  14  15  17  18  19  20  25  30  35  40
层序遍历:20  14  25  4   15  35  2   10  17  30  40  1   6   19  9   18
请输入要删除的节点值:17
删除后root = 20 proot = 00A8FA6C
中序遍历:1   2   4   6   9   10  14  15  18  19  20  25  30  35  40
层序遍历:20  14  25  4   15  35  2   10  19  30  40  1   6   18  9
请输入要删除的节点值:20
删除后root = 19 proot = 00A8FA6C
中序遍历:1   2   4   6   9   10  14  15  18  19  25  30  35  40
层序遍历:19  14  25  4   15  35  2   10  18  30  40  1   6   9
请输入要删除的节点值:14
删除后root = 19 proot = 00A8FA6C
中序遍历:1   2   4   6   9   10  15  18  19  25  30  35  40
层序遍历:19  10  25  4   15  35  2   6   18  30  40  1   9
******
*/
# include <stdio.h>
# include <stdlib.h>
# define ElemType int
# define MAX_SIZE 50
typedef struct BSTreeNode{
    ElemType data;
    struct BSTreeNode * lchild;
    struct BSTreeNode * rchild;
}Node, *pNode;
void InOrderTree(pNode root);//中序遍历二叉排序树
void LevelOrder(pNode root);//层序遍历二叉排序树
pNode CreateTreeNode(ElemType data);//创建二叉排序树的一个节点
void InsertTreeNode(pNode * proot, ElemType data);//向二叉排序树中依序插入一个节点
int TreeHeight(pNode root);//二叉排序树的高度
pNode FindTree(pNode root, ElemType data);//二叉排序树的查找
pNode FindParent(pNode root, ElemType data);//二叉排序树查找父节点
void DeleteTree(pNode * proot, ElemType data);//删除二叉排序树节点
void DestoryTree(pNode * proot);//销毁二叉排序树
int main(void)
{
    pNode root = NULL;
    ElemType test[] = {20, 14, 5, 15, 25, 35, 30, 17, 10, 19, 6, 4 ,40, 18, 2, 9, 1, 7};
    //ElemType test[] = {3,4,2};
    int len = sizeof(test)/sizeof(ElemType);
    for(int i = 0; i < len; i++)
    {
        InsertTreeNode(&root, test[i]);
    }
    printf("中序遍历:");
    InOrderTree(root);
    printf("\n");
    printf("层序遍历:");
    LevelOrder(root);
    printf("\n");
    printf("Treeheight = %d\n", TreeHeight(root));
    printf("请输入待寻找的数字:");
    ElemType x;
    scanf("%d", &x);
    pNode find = FindTree(root, x);
    if(find)
        printf("找到了%d.\n", find->data);
    else
        printf("没找到.\n");
    printf("请输入待寻找父节点的数字:");
    ElemType y;
    scanf("%d", &y);
    pNode findparent = FindParent(root, y);
    if(findparent)
        printf("%d的父节点值为%d\n", y, findparent->data);
    else
        printf("没有父节点.\n");
    ElemType elem;
    for(int i = 0; i < len; i++)
    {    
        printf("请输入要删除的节点值:");
        scanf("%d", &elem);
        DeleteTree(&root, elem);
        printf("删除后root = %d proot = %p\n", root->data, &root);
        printf("中序遍历:");
        InOrderTree(root);
        printf("\n");
        printf("层序遍历:");
        LevelOrder(root);
        printf("\n");
    }
    DestoryTree(&root);
    system("pause");
    return 0;
}
//创建二叉排序树的一个节点
pNode CreateTreeNode(ElemType data)
{
    pNode pNew = (pNode)malloc(sizeof(Node));
    if(NULL == pNew)
        exit(-1);
    pNew->data = data;
    pNew->lchild = NULL;
    pNew->rchild = NULL;
    return pNew;
}
//中序遍历二叉排序树
void InOrderTree(pNode root)
{    
    //递归
    if(NULL == root)
        return;
    InOrderTree(root->lchild);
    printf("%-4d", root->data);
    InOrderTree(root->rchild);
    //非递归-栈
    /*
    if(NULL == root)
        return;
    pNode pStack[MAX_SIZE];
    int top = -1;
    pNode pMove = root;
    while(pMove || top != -1)
    {    
        while(pMove)
        {    
            pStack[++top] = pMove;
            pMove = pMove->lchild;
        }
        if(top != -1)
        {    
            pMove = pStack[top--];
            printf("%-4d", pMove->data);
            pMove = pMove->rchild;
        }
    }
    */
}
//层序遍历二叉排序树
void LevelOrder(pNode root)
{
    if(root != NULL)
    {    
        pNode Queue[MAX_SIZE];//存放树节点地址的队列
        int front = 0, rear = 0;
        pNode pTemp = NULL;
        //根指针入队
        rear = (rear+1) % MAX_SIZE;
        Queue[rear] = root;
        while(front != rear)//当队列不为空时一直循环
        {
            front = (front+1) % MAX_SIZE;//出队
            pTemp = Queue[front];
            printf("%-4d",pTemp->data);
            if(pTemp->lchild != NULL)//左节点指针若不为空则入队
            {
                rear = (rear+1) % MAX_SIZE;
                Queue[rear] = pTemp->lchild;
            }
            if(pTemp->rchild != NULL)//右节点指针若不为空则入队
            {
               rear = (rear+1) % MAX_SIZE;
               Queue[rear] = pTemp->rchild;
            }
        }
    }
} 
//向二叉排序树中依序插入一个节点
void InsertTreeNode(pNode * proot, ElemType data)
{    
    //递归插入
    {
        if(NULL == proot)
            return;
        if(NULL == *proot)
        {
            *proot = CreateTreeNode(data);
            return;
        }
        if(data < (*proot)->data)
            InsertTreeNode(&(*proot)->lchild, data);
        else if(data > (*proot)->data)
            InsertTreeNode(&(*proot)->rchild, data);
        else
            (*proot)->data = data;
    }
    //非递归插入
    /*
    if(NULL == proot)
        return;
    if(NULL == *proot)
    {
        *proot = CreateTreeNode(data);
        return;
    }
    pNode pMove = *proot;
    pNode parent = NULL;
    while(pMove)
    {    
        parent = pMove; 
        if(data < pMove->data)
        {    
            pMove = pMove->lchild;
        }
        else if(data > pMove->data)
        {
            pMove = pMove->rchild;
        }
        else
        {
            pMove->data = data;
            break;
        }
    }
    if(data < parent->data)
        parent->lchild = CreateTreeNode(data);
    else
        parent->rchild = CreateTreeNode(data);
    */
}
//二叉排序树的高度
int TreeHeight(pNode root)
{
    if(NULL == root)
        return 0;
    int lh = TreeHeight(root->lchild);
    int rh = TreeHeight(root->rchild);
    if(lh > rh)
        return lh + 1;
    else
        return rh + 1;
}
//二叉排序树的查找
pNode FindTree(pNode root, ElemType data)
{    
    //递归查找
    if(NULL == root || data == root->data)
        return root;
    if(data < root->data)
        return FindTree(root->lchild, data);
    else
        return FindTree(root->rchild, data);
    //非递归查找
    /*
    pNode pMove = root;
    while(pMove)
    {    
        if(data == pMove->data)
            break;
        else if (data < pMove->data)
            pMove = pMove->lchild;
        else
            pMove = pMove->rchild;
    }
    return pMove;
    */
}
//二叉排序树查找父节点
pNode FindParent(pNode root, ElemType data)
{
    if(NULL == root)
        return NULL;
    pNode pMove = root;
    pNode parent = NULL;
    while(pMove)
    {    
        if(data == pMove->data)
        {
            return parent;
        }
        else if(data < pMove->data)
        {    
            parent = pMove;
            pMove = pMove->lchild;
        }
        else
        {
            parent = pMove;
            pMove = pMove->rchild;
        }
    }
    return NULL;
}
//删除二叉排序树节点
void DeleteTree(pNode * proot, ElemType data)
{    
    if(NULL == *proot)
        return;
    //找到待删除节点的位置pFind
    pNode pFind = FindTree(*proot, data);//找到待删除节点位置
    pNode parent = FindParent(*proot, data);//找到待删除节点的父节点位置
    //1.删除的节点无左右子节点即叶子节点
    if(NULL == pFind->lchild && NULL == pFind->rchild)
    {    
        if(NULL == parent)//如果父节点为空，则删除节点为根节点
        {
            free(pFind);
            pFind = NULL;
            *proot = NULL;
        }
        else
        {
            if(pFind == parent->lchild)
                parent->lchild = NULL;
            if(pFind == parent->rchild)
                parent->rchild = NULL;
            free(pFind);
            pFind = NULL;
        }
    }
    //2.删除的节点只有左节点
    //判断pFind和其父节点的关系后直接删除，并连接其子节点
    else if(pFind->lchild != NULL && pFind->rchild == NULL)
    {    
        if(NULL == parent)//如果父节点为空，则删除节点为根节点
        {
            *proot = pFind->lchild;
            free(pFind);
            pFind = NULL;
        }
        else 
        {
            if(pFind == parent->lchild)//判断pFind是其父节点的左子节点还是右子节点好建立联系
                parent->lchild = pFind->lchild;
            else
                parent->rchild = pFind->lchild;
            free(pFind);
            pFind = NULL;
        }
    }
    //3.删除的节点只有右节点
    //判断pFind和其父节点的关系后直接删除，并连接其子节点
    else if(pFind->rchild != NULL && pFind->lchild == NULL)
    {    
        if(NULL == parent)//如果父节点为空，则删除节点为根节点
        {
            *proot = pFind->rchild;
            free(pFind); 
            pFind = NULL;
        }
        else
        {
            if(pFind == parent->lchild)//判断pFind是其父节点的左子节点还是右子节点好建立联系
                parent->lchild = pFind->rchild;
            else
                parent->rchild = pFind->rchild;
            free(pFind);
            pFind = NULL;
        }
    }
    //4.删除的节点左右节点都有
    //不需要判断父节点为空，即删除节点为根节点为空情况，只需找pFind左子树中的最大值替换,或者右子树的最小值替换,而不是直接删除该节点
    else
    {    
        pNode pDelete = pFind->lchild;//pDelet为左子树中的最大节点
        if(NULL == pDelete->rchild)//如果找到的节点pFind的左子树的根节点的右子节点为空，则其为待删除节点左子树中的最大节点
        {    
            pFind->data = pDelete->data;
            pFind->lchild = pDelete->lchild;
            free(pDelete);
            pDelete = NULL;
        }
        else//如果找到的节点pFind的左子树的根节点的右子节点不为空，则需要一直向右找到pFind的左子树中的最大节点pDelet
        {    
            pNode pMove = pFind;//临时移动父节点指针
            while(pDelete->rchild)//当pDelet的右子节点为空时则找到最大节点
            {    
                pMove = pDelete;
                pDelete = pDelete->rchild;
            }
            pFind->data = pDelete->data;
            pMove->rchild = pDelete->lchild;
            free(pDelete);
            pDelete = NULL;
        }
    }
}
//销毁二叉排序树
void DestoryTree(pNode * proot)
{
    if(NULL == proot || NULL == *proot)
        return;
    DestoryTree(&(*proot)->lchild);
    DestoryTree(&(*proot)->rchild);
    free(*proot);
    *proot = NULL;
}