二叉树的遍历有两个基本问题：给定一颗树，输出其特定形式的遍历结果；给定一个或几个遍历，重建这棵树。第一个问题比较简单，而第二个问题则相对较复杂。本文就对这两个问题进行一个总结。
二叉树的节点使用以下结构体定义：
1
2
3
4
| typedef struct Node_s {
int element;
struct Node_s * left, * right;
} Node;
|
输出遍历结果
前序遍历（Preorder Traversal）
1
2
3
4
5
6
7
| void PreorderTraversal(Node * T) {
if (!T)
return;
printf("%d ", T->element);
PreorderTraversal(T->left);
PreorderTraversal(T->right);
}
|
中序遍历（Inorder Traversal）
1
2
3
4
5
6
7
| void InorderTraversal(Node * T) {
if (!T)
return;
InorderTraversal(T->left);
printf("%d ", T->element);
InorderTraversal(T->right);
}
|
后序遍历（Postorder Traversal）
1
2
3
4
5
6
7
| void PostorderTraversal(Node * T) {
if (!T)
return;
PostorderTraversal(T->left);
PostorderTraversal(T->right);
printf("%d ", T->element);
}
|
层序遍历（Levelorder Traversal）
与其它遍历方法不同，层序遍历是一种广度优先搜索（BFS），一般需要使用队列实现，此处使用了STL中的<deque>结构。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void LevelorderTraversal(Node * T) {
if (!T)
return;
deque<Node *> buf;
buf.push_back(T);
while (!buf.empty()) {
Node * currentNode = buf.front();
buf.pop_front();
cout << currentNode->element << " ";
if (currentNode->left)
buf.push_back(currentNode->left);
if (currentNode->right)
buf.push_back(currentNode->right);
}
}
|
根据遍历结果重建树
一般二叉树
对于一般二叉树来说，只给定任何一种遍历都无法唯一的确定树的结构，需要且仅需要给定中序遍历+另一种其他遍历才能唯一的确定树的结构，下面给出树的重建方法。
中序 + 前序
通过前序遍历可以找出树的根节点，再根据中序遍历确定左右子树元素个数，之后就可以对遍历序列进行划分，迭代处理左右子树了。
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
| Node * InPreRebuild(vector<int> inorder, vector<int> preorder) {
Node * T = new Node();
T->element = preorder[0];
vector<int>::iterator root = find(inorder.begin(), inorder.end(), T->element);
int left = root - inorder.begin();
int right = inorder.end() - root - 1;
if (left > 0) {
T->left = InPreRebuild(vector<int>(inorder.begin(), inorder.begin() + left),
vector<int>(preorder.begin() + 1, preorder.begin() + left + 1));
} else {
T->left = NULL;
}
if (right > 0) {
T->right = InPreRebuild(vector<int>(inorder.end() - right, inorder.end()),
vector<int>(preorder.end() - right, preorder.end()));
} else {
T->right = NULL;
}
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
| Node * InPostRebuild(vector<int> inorder, vector<int> postorder) {
Node * T = new Node();
T->element = *(postorder.end() - 1);
vector<int>::iterator root = find(inorder.begin(), inorder.end(), T->element);
int left = root - inorder.begin();
int right = inorder.end() - root - 1;
if (left > 0) {
T->left = InPostRebuild(vector<int>(inorder.begin(), inorder.begin() + left),
vector<int>(postorder.begin(), postorder.begin() + left));
} else {
T->left = NULL;
}
if (right > 0) {
T->right = InPostRebuild(vector<int>(inorder.end() - right, inorder.end()),
vector<int>(postorder.end() - right - 1, postorder.end() - 1));
} else {
T->right = NULL;
}
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
| Node * InLevelRebuild(vector<int> inorder, vector<int> levelorder) {
Node * T = new Node();
vector<int>::iterator root;
for (auto it = levelorder.begin(); it != levelorder.end(); it++) {
root = find(inorder.begin(), inorder.end(), *it);
if (root != inorder.end()) {
T->element = *root;
break;
}
}
int left = root - inorder.begin();
int right = inorder.end() - root - 1;
if (left > 0) {
T->left = InLevelRebuild(vector<int>(inorder.begin(), inorder.begin() + left),
levelorder);
} else {
T->left = NULL;
}
if (right > 0) {
T->right = InLevelRebuild(vector<int>(inorder.end() - right, inorder.end()),
levelorder);
} else {
T->right = NULL;
}
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
| Node * PreRebuild(vector<int> preorder) {
Node * T = new Node();
T->element = preorder[0];
vector<int>::iterator partition = preorder.begin() + 1;
for (; partition != preorder.end(); partition++) {
if (*partition > T->element)
break;
}
if (partition - preorder.begin() - 1 > 0) {
T->left = PreRebuild(vector<int>(preorder.begin() + 1, partition));
} else {
T->left = NULL;
}
if (preorder.end() - partition > 0) {
T->right = PreRebuild(vector<int>(partition, preorder.end()));
} else {
T->right = NULL;
}
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
| Node * PostRebuild(vector<int> postorder) {
Node * T = new Node();
T->element = *(postorder.end() - 1);
vector<int>::iterator partition = postorder.begin();
for (; partition != postorder.end() - 1; partition++) {
if (*partition > T->element)
break;
}
if (partition - postorder.begin() > 0) {
T->left = PostRebuild(vector<int>(postorder.begin(), partition));
} else {
T->left = NULL;
}
if (postorder.end() - partition - 1 > 0) {
T->right = PostRebuild(vector<int>(partition, postorder.end() - 1));
} else {
T->right = NULL;
}
return T;
}
|
层序
思路也是一样的，只是因为层序遍历中，左右子树的元素是混杂在一起的，直接划分并不方便，所以这里新建了两个vector，将对应的元素放入其中即可。
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
| Node * LevelRebuild(vector<int> levelorder) {
Node * T = new Node();
T->element = levelorder[0];
vector<int> left, right;
for (auto it = levelorder.begin(); it != levelorder.end(); it++) {
if (*it < T->element) {
left.push_back(*it);
} else if (*it > T->element) {
right.push_back(*it);
}
}
if (!left.empty()) {
T->left = LevelRebuild(left);
} else {
T->left = NULL;
}
if (!right.empty()) {
T->right = LevelRebuild(right);
} else {
T->right = NULL;
}
return T;
}
|
总结
根据遍历结果重建二叉树的算法虽然有很多变体，不过其核心思想都是一样的：先找出根节点，之后将遍历结果划分为左右子树对应的部分，最后递归求解。无法唯一确定二叉树的情况都是因为无法唯一确定根节点或无法划分左右子树。
参考资料：
根据前中后序和层序重建二叉树
