二叉树的层次遍历算法

二叉树的层次遍历，也称为广度优先遍历（Breadth-First Search, BFS），是一种按照从上到下、从左到右的顺序访问二叉树中所有节点的算法。它使用队列数据结构来存储当前层的所有节点，然后逐层推进，直到遍历完整棵树。

以下是层次遍历的基本步骤：
1. 创建一个空队列，并将根节点（如果存在）放入队列中。
2. 当队列不为空时，执行以下操作：
a. 弹出队列的第一个元素作为当前节点。
b. 访问该节点（通常会打印或存储节点值）。
c. 如果当前节点有左子节点，将其添加到队列的末尾。
d. 如果当前节点有右子节点，也将其添加到队列的末尾。
3. 重复步骤2，直到队列为空。

相关问题

二叉树层次遍历算法c

二叉树的层次遍历算法可以通过队列来实现。首先将根节点入队，然后进入循环，循环条件为队列不为空。在循环中，首先将队首节点出队并访问该节点，然后将该节点的左子节点和右子节点（如果有）依次入队。重复这个过程直到队列为空。这样就可以按层次顺序遍历二叉树了。

以下是二叉树层次遍历算法的C代码示例：

#include <stdio.h>
#include <stdlib.h>

// 二叉树节点的结构定义
typedef struct BTnode {
    char element;
    struct BTnode *left;
    struct BTnode *right;
} BTnode;

// 层次遍历函数
void levelOrderTraversal(BTnode *root) {
    if (root == NULL) {
        return;
    }
    
    // 创建一个队列，并将根节点入队
    BTnode *queue[100];
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    while (front < rear) {
        // 出队并访问节点
        BTnode *node = queue[front++];
        printf("%c ", node->element);
        
        // 将左子节点和右子节点入队
        if (node->left != NULL) {
            queue[rear++] = node->left;
        }
        if (node->right != NULL) {
            queue[rear++] = node->right;
        }
    }
}

int main() {
    // 创建一个二叉树（示例）
    BTnode *root = (BTnode*)malloc(sizeof(BTnode));
    BTnode *node1 = (BTnode*)malloc(sizeof(BTnode));
    BTnode *node2 = (BTnode*)malloc(sizeof(BTnode));
    BTnode *node3 = (BTnode*)malloc(sizeof(BTnode));
    BTnode *node4 = (BTnode*)malloc(sizeof(BTnode));
    
    root->element = 'A';
    node1->element = 'B';
    node2->element = 'C';
    node3->element = 'D';
    node4->element = 'E';
    
    root->left = node1;
    root->right = node2;
    node1->left = node3;
    node1->right = NULL;
    node2->left = NULL;
    node2->right = node4;
    node3->left = NULL;
    node3->right = NULL;
    node4->left = NULL;
    node4->right = NULL;
    
    // 层次遍历二叉树
    levelOrderTraversal(root);
    
    return 0;
}

以上是二叉树层次遍历算法的C代码实现。你可以根据需要进行修改和扩展。

二叉树层次遍历算法代码实现c语言

以下是C语言实现二叉树层次遍历算法的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 二叉树结点结构体
typedef struct node {
    int data;           // 结点数据
    struct node *left;  // 左子树结点指针
    struct node *right; // 右子树结点指针
} Node, *Tree;

// 队列结构体
typedef struct queue {
    Tree data;          // 队列元素数据
    struct queue *next; // 下一个队列元素指针
} Queue, *Stack;

// 初始化队列
void initQueue(Queue **queue) {
    *queue = (Queue *) malloc(sizeof(Queue));
    (*queue)->next = NULL;
}

// 判断队列是否为空
int isQueueEmpty(Queue *queue) {
    return (queue->next == NULL);
}

// 入队
void enqueue(Queue *queue, Tree data) {
    Queue *newNode = (Queue *) malloc(sizeof(Queue));
    newNode->data = data;
    newNode->next = NULL;

    Queue *p = queue;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = newNode;
}

// 出队
Tree dequeue(Queue *queue) {
    Queue *p = queue->next;
    Tree data = p->data;
    queue->next = p->next;
    free(p);
    return data;
}

// 二叉树层次遍历
void levelOrderTraversal(Tree tree) {
    if (!tree) {
        return;
    }

    Queue *queue;
    initQueue(&queue);
    enqueue(queue, tree);

    while (!isQueueEmpty(queue)) {
        Tree node = dequeue(queue);
        printf("%d ", node->data);

        if (node->left) {
            enqueue(queue, node->left);
        }
        if (node->right) {
            enqueue(queue, node->right);
        }
    }
}

// 测试代码
int main() {
    // 构造二叉树
    Tree tree = (Tree) malloc(sizeof(Node));
    tree->data = 1;
    tree->left = (Tree) malloc(sizeof(Node));
    tree->left->data = 2;
    tree->left->left = NULL;
    tree->left->right = NULL;
    tree->right = (Tree) malloc(sizeof(Node));
    tree->right->data = 3;
    tree->right->left = NULL;
    tree->right->right = NULL;
    tree->left->left = (Tree) malloc(sizeof(Node));
    tree->left->left->data = 4;
    tree->left->left->left = NULL;
    tree->left->left->right = NULL;
    tree->right->right = (Tree) malloc(sizeof(Node));
    tree->right->right->data = 5;
    tree->right->right->left = NULL;
    tree->right->right->right = NULL;

    // 层次遍历
    levelOrderTraversal(tree);

    return 0;
}

以上是一个基于队列实现的二叉树层次遍历算法的 C 语言示例代码。在该示例代码中，主要包括了初始化队列、判断队列是否为空、入队、出队等队列操作函数，以及二叉树层次遍历函数 levelOrderTraversal。在 levelOrderTraversal 函数中，我们首先将根节点入队，然后进行循环遍历，每次出队一个结点，并将该结点的左右子树入队，直到队列为空为止，期间找到的各个结点就是二叉树的层次遍历结果。