Tree Traversal
Tree traversal is a process of visiting each node in the tree exactly once in some order.
树的遍历有2种方式，Breadth-first（广度优先）和Depth-first（深度优先）。
Breadth-first（广度优先）
按照广度优先，对二叉树的遍历方式主要是Level-order（层序遍历）。
Level-order（层序遍历）
层序遍历即对一个二叉树每层从上到下，从左到右进行遍历。
上图层序遍历顺序即为F D J B E G K A C I H.
实现
用队列可以实现层序遍历。因为队列有First-In-First-Out(FIFO)原则，我们可以先让root进入队列，在访问节点时，让其左右节点进入队列。
实现层序遍历的代码如下：
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include<queue>
void LevelOrder(BstNode* root) {
if (root == NULL)return;
queue<BstNode*> Q;
Q.push(root);
while (!Q.empty()) {
BstNode* current = Q.front();
cout << current->data << " ";
if (current->left != NULL)Q.push(current->left);
if (current->right != NULL)Q.push(current->right);
Q.pop();
}
}
|
Depth-first（深度优先）
深度优先有三个排序方法，Preorder（前序）、Inorder（中序）和Postorder（后序）。
| 类型 |
Order |
| Preorder |
<root><left><right>(DLR) |
| Inorder |
<left><root><right>(LDR) |
| Postorder |
<left><right><root>(LRD) |
上图三种不同方式的排列顺序分别为：
Preorder: F D B A C E J G I H K
Inorder: A B C D E F G H I J K
Postorder: A C B E D H I G K J F
实现
三种顺序都可以用递归来简洁地写出，代码如下：
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void Preorder(BstNode* root) {
if (root == NULL)return;
printf("%d ", root->data);
Preorder(root->left);
Preorder(root->right);
}
void Inorder(BstNode* root) {
if (root == NULL)return;
Inorder(root->left);
printf("%d ", root->data);
Inorder(root->right);
}
void Postorder(BstNode* root) {
if (root == NULL)return;
Postorder(root->left);
Postorder(root->right);
printf("%d ", root->data);
}
|
最后附上完整代码，输出树的高度，层序遍历，前序，中序，后序
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
| #include<iostream>
#include<queue>
using namespace std;
struct BstNode {
int data;
BstNode* left;
BstNode* right;
};
void LevelOrder(BstNode* root) {
if (root == NULL)return;
queue<BstNode*> Q;
Q.push(root);
while (!Q.empty()) {
BstNode* current = Q.front();
cout << current->data << " ";
if (current->left != NULL)Q.push(current->left);
if (current->right != NULL)Q.push(current->right);
Q.pop();
}
printf("\n");
}
void Preorder(BstNode* root) {
if (root == NULL)return;
printf("%d ", root->data);
Preorder(root->left);
Preorder(root->right);
}
void Inorder(BstNode* root) {
if (root == NULL)return;
Inorder(root->left);
printf("%d ", root->data);
Inorder(root->right);
}
void Postorder(BstNode* root) {
if (root == NULL)return;
Postorder(root->left);
Postorder(root->right);
printf("%d ", root->data);
}
BstNode* GetNewNode(int data) {
BstNode* NewNode = new BstNode();
NewNode->data = data;
NewNode->left = NewNode->right = NULL;
return NewNode;
}
BstNode* Insert(BstNode* root,int data) {
if (root == NULL)
root = GetNewNode(data);
else if (data <= root->data) {
root->left = Insert(root->left, data);
}
else
root->right = Insert(root->right, data);
return root;
}
int max(int a, int b) {
if (a > b)return a;
else return b;
}
int FindHeight(BstNode* root) {
if (root == NULL) {
return -1;
}
return max(FindHeight(root->left), FindHeight(root->right)) + 1;
}
int main() {
BstNode* root = NULL;
root = Insert(root,3);
root = Insert(root, 6);
root = Insert(root, 2);
root = Insert(root, 1);
root = Insert(root, 7);
root = Insert(root, 5);
root = Insert(root, 8);
root = Insert(root, 4);
printf("Height of tree is %d\n", FindHeight(root));
cout << "LevelOrder:"; LevelOrder(root);
cout << "Preorder:"; Preorder(root); cout << endl;
cout << "Inorder:"; Inorder(root); cout << endl;
cout << "Postorder:"; Postorder(root);
return 0;
}
|