数据结构(5.3_2)——二叉树的层次遍历

代码实现：

//层次遍历
void LevelOrder(BiTNode T) {
    LinkQueue Q; // 声明一个队列Q，用于存储遍历过程中需要访问的节点
    InitQueue(&Q); // 初始化队列Q，设置头结点和尾指针
    BiTree p; // 声明一个指针p，用于在遍历过程中指向当前访问的节点
    EnQueue(&Q, &T); // 将根节点T的地址入队，开始层次遍历
    while (!IsEmpty(Q)) { // 当队列不为空时，继续进行层次遍历
        DeQueue(&Q, &p); // 将队头元素出队，并通过指针p获取出队节点的地址
        visit(p); // 访问节点p，通常是指打印节点的值
        if (p->lchild != NULL) // 如果当前节点p有左孩子
            EnQueue(&Q, p->lchild); // 将左孩子入队，以便后续访问
        if (p->rchild != NULL) // 如果当前节点p有右孩子
            EnQueue(&Q, p->rchild); // 将右孩子入队，以便后续访问
    }
}

注意：存的是指针而不是结点

其他函数的实现：

// 创建一个新节点
BiTree CreateNode(int value) {
    BiTree new_node = (BiTree)malloc(sizeof(BiTNode));
    if (new_node != NULL) {
        new_node->data.value = value;
        new_node->lchild = NULL;
        new_node->rchild = NULL;
    }
    return new_node;
}
void InitQueue(LinkQueue *Q) {
    //初始化时 front、rear 都指向头结点
    Q->front = Q->rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q->front->next = NULL;
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q){
    if (Q.front == Q.rear) {
        return true;
    }
    else {
        return false;
    }
    }
//新元素入队(带头结点)
void EnQueue(LinkQueue* Q, BiTNode *x) {
    LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q->rear->next = s;//新结点插入到rear之后
    Q->rear = s;//修改表尾指针
}
//队头元素出队(带头结点)
bool DeQueue(LinkQueue *Q, BiTNode* x) {
    if (Q->front == Q->rear) {
        return false;//空队
    }
    else {
        LinkNode* p = Q->front->next;//让p指针指向要删除的结点(头结点的后一个结点)
        x = p->data;//用变量x返回队头元素
        Q->front->next = p->next;//修改头结点的next指针
        if (Q->rear == p) {//此次是最后一个结点出队
            Q->rear = Q->front;//修改rear指针
        }
        free(p);//释放结点空间
        return true;
    }
}