二叉树的遍历
二叉树是一种非常重要的数据结构，很多其它数据结构都是基于二叉树的基础演变而来的。
所谓遍历 Traversal 是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。
对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序遍历三种方法，广度遍历即我们平常所说的层次遍历。因为树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁，而对于广度遍历来说，需要其他数据结构的支撑。
四种遍历的主要思想是：
其中，前、中、后续指的是「根节点」的遍历顺序，例如前序遍历是先遍历根节点。
以下为一棵二叉树不同的遍历顺序以及实现方法（非递归实现 / 递归实现）：
1
2
3
4
5
6
7
8
9
10
| 1
/ \
2 3
/ \ \
4 5 6
层次遍历顺序：[1 2 3 4 5 6] / 非递归实现：队列 + BFS
前序遍历顺序：[1 2 4 5 3 6] / 非递归实现：栈，递归实现：DFS
中序遍历顺序：[4 2 5 1 3 6] / 非递归实现：栈，递归实现：DFS
后序遍历顺序：[4 5 2 6 3 1] / 非递归实现：栈，递归实现：DFS
|
层次遍历使用 BFS 实现，利用的就是 BFS 一层一层遍历的特性，而前序、中序、后序遍历利用了 DFS 实现。
前序、中序、后序遍只是在对节点访问的顺序有一点不同，其它都相同。
下面直接从 Leetcode 练习题，学习二叉树的不同遍历方法。
二叉树的层序遍历
题目链接：637. 二叉树的层平均值
题目 ：给定一个非空二叉树，返回一个由每层节点平均值组成的数组。
1
2
3
4
5
6
7
8
| 输入:
3
/ \
9 20
/ \
15 7
输出: [3, 14.5, 11]
解释: 第 0 层的平均值是 3, 第 1 层是 14.5, 第 2 层是 11. 因此返回 [3, 14.5, 11].
|
层序遍历 ：利用队列实现二叉树的层序遍历。
python 双端队列实现二叉树的层序遍历：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| def averageOfLevels(self, root: TreeNode) -> List[float]:
if root == None:
return 0
import collections
queue = collections.deque()
queue.append(root)
res = []
while queue:
size = len(queue)
sum, tmp_size = 0, size
while size > 0:
node = queue.popleft()
size -= 1
sum += node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(sum / tmp_size)
return res
|
C 语言实现基于链表的队列，然后基于队列实现二叉树的层序遍历：
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
|
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
typedef struct Node {
struct TreeNode *data;
struct Node *next;
} Node;
typedef struct Queue {
int size;
Node *front;
Node *rear;
} Queue;
Node *createNode(struct TreeNode *data) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
Queue* createQueue() {
Queue *queue = (Queue *)malloc(sizeof(Queue));
queue->front = NULL;
queue->rear = NULL;
queue->size = 0;
return queue;
}
bool isEmpty(Queue *queue) {
return queue->size == 0;
}
void enQueue(Queue *queue, struct TreeNode *data) {
Node *newNode = createNode(data);
if (isEmpty(queue)) {
queue->front = queue->rear = newNode;
} else {
queue->rear->next = newNode;
queue->rear = newNode;
}
queue->size += 1;
}
struct TreeNode *deQueue(Queue* queue) {
if (isEmpty(queue)) {
return NULL;
}
Node *temp = queue->front;
struct TreeNode *data = temp->data;
queue->front = queue->front->next;
queue->size -= 1;
free(temp);
return data;
}
double* averageOfLevels(struct TreeNode* root, int* returnSize){
double *ans = (double *)malloc(10000 * sizeof(double));
Queue *queue = createQueue();
enQueue(queue, root);
*returnSize = 0;
while (!isEmpty(queue)) {
int size = queue->size;
int tmp_size = size;
double sum = 0;
while (size-- > 0) {
struct TreeNode *node = deQueue(queue);
sum += node->val;
if (node->left) {
enQueue(queue, node->left);
}
if (node->right) {
enQueue(queue, node->right);
}
}
ans[(*returnSize)++] = sum / tmp_size;
}
return ans;
}
|
