数据结构(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;}
}