广度优先遍历或层次遍历(level-order traversal)中，确定节点访问次序的原则概括为：先上后下，先左后右。
实现：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
114#include <stdio.h>
#include <stdlib.h>
typedef struct BinNode{
char data;
struct BinNode *lchild, *rchild;
}BinNode, *BinTree;
typedef BinTree QElemType;
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
int InitQueue(LinkQueue &Q);
int EnQueue(LinkQueue &Q, QElemType e);
int DeQueue(LinkQueue &Q, QElemType &e);
int QueueEmpty(LinkQueue Q);
//'#'表示根节点
void createBinTree(BinTree &T){
char ch;
scanf_s("%c", &ch);
if (ch == '#'){
T = NULL;
}
else{
if (!(T = (BinNode*)malloc(sizeof(BinNode)))){
exit(-1);
}
T->data = ch;
printf("数据%c\n", T->data);
createBinTree(T->lchild);
createBinTree(T->rchild);
}
}
/*递归实现二叉树的遍历方法*/
void preOrderTraverse(BinTree &T){
if (T){
printf("%c", T->data);
preOrderTraverse(T->lchild);
preOrderTraverse(T->rchild);
}
}
/*二叉树的层次遍历*/
int LevelOrderTraverse(BinTree &T){
LinkQueue Q;
InitQueue(Q);
EnQueue(Q, T);
while (!QueueEmpty(Q)){
BinTree p;
DeQueue(Q,p);
printf("%c", p->data);
if (p->lchild)
EnQueue(Q,p->lchild);
if (p->rchild){
EnQueue(Q,p->rchild);
}
}
return 1;
}
int main(){
BinTree T;
createBinTree(T);
printf("递归版本的先序遍历");
preOrderTraverse(T);
printf("层次遍历版本:\n");
LevelOrderTraverse(T);
return 0;
}
int InitQueue(LinkQueue &Q){
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if (!Q.front)
exit(-1);
Q.front->next = NULL;
return 1;
}
int EnQueue(LinkQueue &Q, QElemType e){
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if (!p){
exit(-1);
}
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return 1;
}
int DeQueue(LinkQueue &Q, QElemType &e){
if (Q.front == Q.rear)
return -1;
QueuePtr p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)
Q.rear = Q.front;
free(p);
return 1;
}
int QueueEmpty(LinkQueue Q){
return (Q.front->next ==NULL && Q.rear->next == NULL) ? 1 : 0;
}