2021_1

//实现对孩子兄弟树的遍历操作 要求对于任意指定节点(假设唯一)，可以得到其孩子，兄弟，与双亲
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int Emtpye;

// #define Max 514;

typedef struct CSNode{
    Emtpye data;
    struct CSNode *firstChild, *nextSibling;
} CSNode, *CSTree;

typedef struct linkNode{
    CSNode *data;
    struct linkNode *next;
} linkNode;

struct link{                   //用于存储返回的结果结构体
    linkNode *childs;
    linkNode *sibling;
    CSNode *parent;
};

struct link *findMessage(CSNode *, CSNode *);
int createCSTree(CSTree *);
void preorder(CSTree);
CSNode *find(CSTree, Emtpye);

int main(void){

    CSTree t = (CSTree)malloc(sizeof(CSNode));
    createCSTree(&t);
    preorder(t);
    printf("\n");

    CSNode *trage = find(t, 5);

    struct link *ret = findMessage(t, trage);

    if(ret){
        if(ret&&ret->parent){
            printf("parent is :%d\n", ret->parent->data);
        }
        else{
            printf("Not parent!\n");
        }

        linkNode *childs = ret->childs->next;               //跳过头节点，获取有效信息节点

        if(childs){
            printf("childs is : ");
            while(childs){
                printf("%d\t", childs->data->data);
                childs = childs->next;
            }
            printf("\n");
        }
        else{
            printf("Not childs!\n");
        }

        linkNode *sibling = ret->sibling->next;

        if(sibling){
            printf("sibling is : ");
            while(sibling){
                printf("%d\t", sibling->data->data);
                sibling = sibling->next;
            }
            printf("\n");
        }
        else{
            printf("Not sibling!\n");
        }
    }
    return 0;
}

struct link* findMessage(CSTree p,CSNode* trage){
    int front = -1, rear = -1, last = 0;                            //队头、队尾指针、用于控制层次遍历标记

    struct link *ans = (struct link *)malloc(sizeof(struct link));  //转载指定节点信息的自定义结构体
    ans->childs = (linkNode *)malloc(sizeof(linkNode));
    ans->childs->next = NULL;
    ans->sibling = (linkNode *)malloc(sizeof(linkNode));
    ans->sibling->next = NULL;
    ans->parent = NULL;

    CSTree queue[514] = {NULL,};                                    //创建层次遍历孩子兄弟树的队列
    queue[++rear] = p;                                             //根节点入队
    CSNode *tmp_parent = NULL, *tmp_childs = NULL;
    CSNode *node = NULL;                                           //工作指针
    bool found = false;                                            //用于标记是否找到目标节点

    /** 思想：
     * 当指定节点 node 入队时
     *      刚出队的节点，就是 node 的双亲结点
     *      此次一起入队的所有节点，都是node的兄弟节点
     * 当指定节点出队的时候，需换便利 node 的左孩子的所有兄弟节点，得到 node 的所有孩子节点
     */
    while (front < rear){
        node = queue[++front];                    //结点出队
        tmp_parent = node;                       //用临时节点标记每轮循环出队的节点

        /* 插入目标节点的孩子节点 */
        if(trage==node){                        //队头节点为目标节点
            if(node->firstChild){              //存在孩子
                linkNode *r = ans->childs;     //对存储结构体(孩子)使用尾插法插入
                tmp_childs = node->firstChild;
                while(tmp_childs){             //遍历目标节点的左孩子及左孩子的兄弟节点
                    r->next = (linkNode *)malloc(sizeof(linkNode));
                    r->next->data = (CSNode *)malloc(sizeof(CSNode));
                    r->next->data->data = tmp_childs->data;
                    r->next->data->firstChild = r->next->data->nextSibling = NULL;
                    r->next->next = NULL;
                    r = r->next;
                    tmp_childs = tmp_childs->nextSibling;
                }
                tmp_childs = NULL;
            }
        }
        if(node->firstChild){                         //若刚出队的节点有一个孩子
            node = node->firstChild;                 //获取刚出队的节点的第一个孩子
            queue[++rear] = node;                   //左孩子孩子入队
            if(trage==node){                       //左孩子孩子便是目标节点
                found = true;
            }
            while(node->nextSibling){           //将左孩子的所有兄弟节点入队(若有)
                node = node->nextSibling;
                queue[++rear] = node;
                if(trage==node){                //如果目标节点夹在兄弟节点之中
                      found = true;
                }
            }
        }
        /* 插入目标节点的兄弟节点 */
        if(found){
            ans->parent = tmp_parent;
            linkNode *r = ans->sibling;                             //对存储结构体(兄弟)使用尾插法插入
            for (int i = last + 1; i <= rear;i++){                 //last表示当前遍历到的层的最后一个叶子节点(在队列中的下标)
                if(trage->data==queue[i]->data) continue;          //该节点为目标节点自身，跳过(自己不是自己的兄弟节点)
                r->next = (linkNode *)malloc(sizeof(linkNode));
                r->next->data = (CSNode *)malloc(sizeof(CSNode));
                r->next->data->firstChild = r->next->data->nextSibling = NULL;
                r->next->data->data = queue[i]->data;             //复制数据
                r->next->next = NULL;
                r = r->next;
            }
            found = false;                                        //重置指针，防止二次覆盖
        }
        if(front == last)                                         //遍历完一层了，last指向下一层最后一个叶子节点(在队列中的下标)
            last = rear;
    }
    return ans;
}

//建树
int createCSTree(CSTree *p){                             //类似于树的先根遍历
    if(!p){                                             //空树
        return 0;
    }
    int k;
    printf("请输入当前节点数值，-1代表空树\n");
    scanf("%d", &k);
    getchar();
    if (k == -1){
        (*p) = NULL;
        return 0;
    }
    (*p)->data = k;
    (*p)->firstChild = (CSNode*)malloc(sizeof(CSNode));
    (*p)->nextSibling = (CSNode*)malloc(sizeof(CSNode));
    printf("请输入长子节点:\n");
    if (createCSTree(&((*p)->firstChild)) == 0){
        free((*p)->firstChild);
        (*p)->firstChild = NULL;
    }
    printf("请输入兄弟节点:\n");
    if (createCSTree(&((*p)->nextSibling)) == 0){
        free((*p)->nextSibling);
        (*p)->nextSibling = NULL;
    }
    return 1;
}

//先根遍历
void preorder(CSTree t){
    if(t){
        printf("%d\t", t->data);
        CSNode *p = t->firstChild;
        preorder(p);
        while (p){
            p = p->nextSibling;
            preorder(p);
        }
    }
}

//根据指定序号返回目标节点指针
CSNode *find(CSTree t, Emtpye trage){
    if(t&&t->data==trage)
        return t;
    if (t){
        CSNode *p = t->firstChild;
        CSNode *node = find(p, trage);

        if(node)
            return node;
        while (p){
            p = p->nextSibling;
            node = find(p, trage);
            if(node)
                return node;
        }
        return NULL;
    }
    return NULL;
}