【数据结构】二叉树（9）

typedef char ElemType;
struct BTNode
{
    ElemType data;
    struct BTNode * pL_child;
    struct BTNode * pR_child;
};

//关于队列
struct Node
{
    struct BTNode * data;
    struct Node * pNext;
};
struct LinkQueue
{
    struct Node * front;
    struct Node * rear;
};

void init_queueLink(struct LinkQueue * pLQ)
{
    pLQ->front = pLQ->rear = (struct Node *) malloc(sizeof (struct Node));
    if (!pLQ->front)
        exit(-1);
    pLQ->front->pNext = NULL;
}
void destroy_queueLink(struct LinkQueue * pLQ)
{
    while (pLQ->front)
    {
        pLQ->rear = pLQ->front->pNext;
        free(pLQ->front);
        pLQ->front = pLQ->rear;
    }
}
void en_queueLink(struct LinkQueue * pLQ, struct BTNode * val)
{
    struct Node * p;
    p = (struct Node *) malloc(sizeof (struct Node));
    if (!p)
        exit(-1);
    p->data = val;
    p->pNext = NULL;
    pLQ->rear->pNext = p;
    pLQ->rear = p;

}
bool is_emptyLink(struct LinkQueue * pLQ)
{
    if (pLQ->front->pNext == NULL)
        return true;
    else
        return false;
}
bool out_queueLink(struct LinkQueue * pLQ, struct BTNode ** val)
{
    if (is_emptyLink(pLQ))
        return false;
    struct Node * p = pLQ->front->pNext;
    struct Node * q = p->pNext;
    *val = p->data;
    pLQ->front->pNext = q;
    if (pLQ->rear == p)
        pLQ->rear = pLQ->front;
    free(p);

    return true;
}

//创建二叉树
struct BTNode * create_biTree()
{
    ElemType data;
    struct BTNode * T;
    fflush(stdout);
    scanf("%c",&data);		//	输入数据
    getchar();
    if(data == '#')
    {
        return NULL;
    }
    else
    {
        T = (struct BTNode *)malloc(sizeof(struct BTNode));
        T->data = data;

        printf("请输入%c的左子树: ",data);
        T->pL_child = create_biTree();
        printf("请输入%c的右子树: ",data);
        T->pR_child = create_biTree();
        return T;
    }
}

//销毁二叉树
void destroy_biTree(struct BTNode ** pT)
{
    if (*pT)
    {
        destroy_biTree(&(*pT)->pL_child);   //递归销毁左子树
        destroy_biTree(&(*pT)->pR_child);   //递归销毁右子树
        free(*pT);
        *pT = NULL;
    }
}

//先序遍历二叉树
void preOrderTraverse(struct BTNode * pT)
{
    if(pT==NULL)
    {
        return;
    }
    printf("%c ", pT->data);
    preOrderTraverse(pT->pL_child);
    preOrderTraverse(pT->pR_child);
}

//中序遍历二叉树
void inOrderTraverse(struct BTNode * pT)
{
    if (pT)
    {
        inOrderTraverse(pT->pL_child);
        printf("%c ", pT->data);
        inOrderTraverse(pT->pR_child);
    }
}

//后序遍历二叉树
void postOrderTraverse(struct BTNode * pT)
{
    if (pT)
    {
        postOrderTraverse(pT->pL_child);
        postOrderTraverse(pT->pR_child);
        printf("%c ", pT->data);
    }
}

//层序遍历二叉树
void levelOrderTraverse(struct BTNode * pT)
{
    struct LinkQueue q;
    struct BTNode * a;
    if (pT)
    {
        init_queueLink(&q);
        en_queueLink(&q, pT);
        while (!is_emptyLink(&q))
        {
            out_queueLink(&q, &a);
            printf("%c ", a->data);
            if (a->pL_child != NULL)
                en_queueLink(&q, a->pL_child);
            if (a->pR_child != NULL)
                en_queueLink(&q, a->pR_child);
        }
        printf("n");
        destroy_queueLink(&q);
    }
}

//5判断二叉树是否为空
bool is_empty_biTree(struct BTNode * pT)
{
    if (pT)
        return false;
    else
        return true;
}

//6返回二叉树的深度
int biTree_depth(struct BTNode * pT)
{
    int i, j;
    if (!pT)
        return 0;
    i = biTree_depth(pT->pL_child);
    j = biTree_depth(pT->pR_child);

    return i > j ? i + 1 : j + 1;
}

//7返回根结点
ElemType root_val(struct BTNode * pT)
{
    if (is_empty_biTree(pT))
        return '#';
    else
    {
        return pT->data;
    }
}

//8返回二叉树中指向元素值为 val 的结点的指针
struct BTNode * pointer(struct BTNode * pT, ElemType val)
{
    struct LinkQueue q;
    struct BTNode * a;
    if (pT)
    {
        init_queueLink(&q);
        en_queueLink(&q, pT);
        while (!is_emptyLink(&q))
        {
            out_queueLink(&q, &a);
            if (a->data == val)
            {
                destroy_queueLink(&q);
                return a;
            }
            if (a->pL_child)
                en_queueLink(&q, a->pL_child);
            if (a->pR_child)
                en_queueLink(&q, a->pR_child);
        }
    }
    return NULL;
}

//返回p所指向结点的值
ElemType value(struct BTNode * p)
{
    return p->data;
}

//返回val的左孩子
ElemType left_child(struct BTNode * pT, ElemType val)
{
    struct BTNode * a;
    if (pT)
    {
        a = pointer(pT, val);
        if (a && a->pL_child)
            return a->pL_child->data;
    }
    return '#';
}

//返回val的右孩子
ElemType right_child(struct BTNode * pT, ElemType val)
{
    struct BTNode * a;
    if (pT)
    {
        a = pointer(pT, val);
        if (a && a->pR_child)
            return a->pR_child->data;
    }
    return '#';
}

//删除p指向某个结点的左或右子树
void delete_child(struct BTNode * p, int LR)
{
    if (p)
    {
        if (LR == 0)
            destroy_biTree(&p->pL_child);
        else if(LR == 1)
            destroy_biTree(&p->pR_child);
    }
}

//返回父节点
ElemType parent(struct BTNode * pT, ElemType val)
{
    struct LinkQueue q;
    struct BTNode * a;
    if (pT)
    {
        init_queueLink(&q);
        en_queueLink(&q, pT);
        while (!is_emptyLink(&q))
        {
            out_queueLink(&q, &a);
            if (a->pL_child && a->pL_child->data == val || a->pR_child && a->pR_child->data == val)
                return a->data;
            else
            {
                if (a->pL_child)
                    en_queueLink(&q, a->pL_child);
                if (a->pR_child)
                    en_queueLink(&q, a->pR_child);
            }
        }
    }
    return '#';
}

//返回左兄弟
ElemType left_sibling(struct BTNode * pT, ElemType val)
{
    ElemType a;
    struct BTNode * p;
    if (pT)
    {
        a = parent(pT, val);
        if (a != '#')
        {
            p = pointer(pT, a);
            if (p->pL_child && p->pR_child && p->pR_child->data == val)
                return p->pL_child->data;
        }
    }
    return '#';
}

//返回右兄弟
ElemType right_sibling(struct BTNode * pT, ElemType val)
{
    ElemType a;
    struct BTNode * p;
    if (pT)
    {
        a = parent(pT, val);
        if (a != '#')
        {
            p = pointer(pT, a);
            if (p->pL_child && p->pR_child && p->pL_child->data == val)
                return p->pR_child->data;
        }
    }
    return '#';
}

//插入子树
bool insert_child(struct BTNode * p, int LR, struct BTNode * c)
{
    if (p)
    {
       if (LR == 0)
       {
           c->pR_child = p->pL_child;
           p->pL_child = c;
       }
       else if (LR == 1)
       {
           c->pR_child = p->pR_child;   //p所指向的结点的原有右子树成为c的右子树
           p->pR_child = c;             //c成为p的右子树
       }
        return true;
    }
    return false;
}

#include 
#include 
#include 
#include 
int main() {
    struct BTNode * T;
    struct BTNode * c;
    //init_biTree(T);
    T = create_biTree();
    c = create_biTree();
    preOrderTraverse(T);
    printf("n");
    levelOrderTraverse(T);
    
    struct BTNode * r = pointer(T, 'B');
    insert_child(r, 1, c);
    preOrderTraverse(T);

    int depth;
    depth = biTree_depth(T);
    printf("n树的深度为:%dn", depth);

    ElemType val_root;
    val_root = root_val(T);
    printf("root_val = %cn", val_root);


    struct BTNode * p = pointer(T, 'C');
    ElemType val;
    val = value(p);
    printf("val_p = %cn", val);

    char val_r;
    char val_l;
    val_l = left_child(T, 'E');
    printf("E的左子节点：%cn", val_l);
    val_r = right_child(T, 'E');
    printf("E的右子节点：%cn", val_r);


    struct BTNode * q = pointer(T, 'E');
    delete_child(q, 1);
    preOrderTraverse(T);

    ElemType val_par;
    val_par = parent(T, 'D');
    printf("val_par = %cn", val_par);
    return 0;
}