利用队列实现对二叉树的层序遍历_队列实现二叉树的层次遍历

初始化二叉树

// 定义一个函数Root，参数为一个指向Tree类型的指针t，返回值为一个指向Tree类型的指针
Tree* Root(Tree* t)
{
    // 初始化左右子树的根节点l和r，都指向传入的根节点t
    Tree* l = t;
    Tree* r = t;

    // 给左子树的根节点l设置数据为'A'
    l->data = 'A';

    // 初始化一个新的节点node
    Tree* node = NULL;

    // 初始化一个整数i为1
    int i = 1;

    // 调用InitTreeNode函数初始化一个新的节点node，并返回该节点的指针
    node = InitTreeNode();

    // 给新节点node的数据设置为'B'
    node->data = 'B';

    // 将新节点node设置为左子树的根节点l
    l->left = node;

    // 将l更新为新节点node
    l = node;

    // 重新初始化一个新的节点node
    node = InitTreeNode();

    // 给新节点node的数据设置为'C'
    node->data = 'C';

    // 将新节点node设置为右子树的根节点r
    l->right = node;

    // 将l更新为新节点node
    l = node;

    // 重新初始化一个新的节点node
    node = InitTreeNode();

    // 给新节点node的数据设置为'D'
    node->data = 'D';

    // 将新节点node设置为左子树的根节点l
    l->left = node;

    // 重新初始化一个新的节点node
    node = InitTreeNode();

    // 给新节点node的数据设置为'E'
    node->data = 'E';

    // 将新节点node设置为右子树的根节点r
    r->right = node;

    // 将r更新为新节点node
    r = node;

    // 重新初始化一个新的节点node
    node = InitTreeNode();

    // 给新节点node的数据设置为'F'
    node->data = 'F';

    // 将新节点node设置为左子树的根节点l
    l->right = node;

    // 重新初始化一个新的节点node
    node = InitTreeNode();

    // 给新节点node的数据设置为'G'
    node->data = 'G';

    // 将新节点node设置为右子树的根节点r
    r->left = node;

    // 重新初始化一个新的节点node
    node = InitTreeNode();

    // 给新节点node的数据设置为'H'
    node->data = 'H';

    // 将新节点node设置为右子树的根节点r
    r->right = node;

    // 返回根节点t
    return t;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

初始化的二叉树结构如下图（图从网上找的）

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
// 定义一个二叉树结构体
typedef struct tree {
    char data; // 数据域
    struct tree* left; // 左子树指针
    struct tree* right; // 右子树指针
} Tree;

// 定义一个节点结构体
typedef struct node {
    struct tree* st; // 指向二叉树的指针
    struct node* next; // 指向下一个节点的指针
} Node;

// 定义一个队列结构体
typedef struct tagQUEUE {
    struct node* front; // 队头指针
    struct node* rear; // 队尾指针
} tagQueue;

// 初始化一个节点
Node* Init() {
    Node* node;
    node = (Node*)malloc(sizeof(Node)); // 分配内存空间
    node->next = NULL; // 初始化next指针为NULL
    memset(&node->st, 0, sizeof(Tree)); // 将二叉树指针所指向的内存区域清零
    return node;
}
// 创建一个队列
tagQueue* CreateQueue() {
    tagQueue* s;
    Node* node;
    node = Init(); // 初始化一个节点
    s = (tagQueue*)malloc(sizeof(tagQueue)); // 分配内存空间
    s->front = s->rear = node; // 初始化队头指针和队尾指针为同一个节点
    return s;
}


// 将一个二叉树入队
void PushQueue(tagQueue* pHead, Tree* root) {
    Node* newNode = Init(); // 初始化新节点
    newNode->st = root; // 将新节点的二叉树指针指向传入的根节点
    pHead->rear->next = newNode; // 将新节点插入到队列尾部
    pHead->rear = newNode; // 更新队尾指针
    // printf("%c入队列！\n", pHead->rear->st->data);
}
// 初始化一个二叉树节点
Tree* InitTreeNode() {
    Tree* t = NULL;
    t = (Tree*)malloc(sizeof(Tree)); // 分配内存空间
    t->left = t->right = NULL; // 初始化左右子树指针为NULL
    memset(&t->data, 0, sizeof(t->data)); // 将节点的数据域清零
    return t;
}

// 弹出队列中的一个节点，并打印其数据域的值
void PopStack(tagQueue* pHead) {
    if (pHead->front == pHead->rear) {
        printf("队列空\n");
    }
    else {
        Node* node;
        node = pHead->front->next; // 获取队头指针的下一个节点
        if (node->st->left != NULL) {
            PushQueue(pHead, node->st->left); // 将左子树入队
        }
        if (node->st->right != NULL) {
            PushQueue(pHead, node->st->right); // 将右子树入队
        }
        printf("%c ", node->st->data); // 打印节点的数据域的值
        if (pHead->front->next == pHead->rear) {
            pHead->rear = pHead->front; // 如果队列中只有一个节点，则更新队尾指针为队头指针
        }
        else {
            pHead->front->next = node->next; // 否则将队头指针的next指针指向当前节点的下一个节点
        }
        free(node);
        PopStack(pHead); // 递归调用PopStack函数，继续弹出下一个节点
    }
}

// 主函数
int main()
{
    // 声明一个指向Tree类型的指针root，并初始化为NULL
    Tree* root = NULL;

    // 调用InitTreeNode函数初始化一个新的节点，并将该节点赋值给root
    root = InitTreeNode();

    // 调用Root函数，传入root作为参数，返回一个新的根节点，并将其赋值给root
    root = Root(root);

    // 声明一个队列头指针head，并调用CreateQueue函数创建一个新的队列
    tagQueue* head = CreateQueue();

    // 调用PushQueue函数将root节点入队
    PushQueue(head, root);

    // 调用PopStack函数弹出队列头部元素，并打印输出
    PopStack(head);
    printf("\n");

    // 再次将root节点入队
    PushQueue(head, root);

    // 再次调用PopStack函数弹出队列头部元素，并打印输出
    PopStack(head);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113