假设已经有了前序遍历和中序遍历的结果，希望通过一个算法重建这棵树。已知遍历结果为字符串，且树的每个节点的value都是一个字符，且各不相同。
如，前序：a b d c e f
中序：d b a e c f
则由前序可知，树的根必定是前序遍历的第一个节点a，再找a在中序中的位置，则可知道中序遍历中a之前的所有节点都是a的左子树，这样，就可以递归建立左子树，同样中序遍历中a右边的序列是a的右子树，递归建立即可。
代码如下：
1 struct NODE {
2 NODE* left;
3 NODE* right;
4 char value;
5 };
6
7 void rebuild_bitree(char *pre_order,
8 char *in_order,
9 int treelen,
10 NODE **root) {
11 assert(root != NULL);
12 if (pre_order == NULL ||
13 in_order == NULL ||
14 treelen <= 0) {
15 return;
16 }
17 if (*root == NULL) {
18 *root = new NODE;
19 }
20 (*root)->value = pre_order[0];
21 (*root)->left = (*root)->right = NULL;
22 int i = 0;
23 for (i = 0; i < treelen; ++i) {
24 if (in_order[i] == pre_order[0]) {
25 break;
26 }
27 }
28 rebuild_bitree(pre_order + 1,
29 in_order,
30 i,
31 &((*root)->left));
32 rebuild_bitree(pre_order + i + 1,
33 in_order + i + 1,
34 treelen - i - 1,
35 &((*root)->right));
36 }
如果已经知道了中序遍历结果和后序遍历结果，那么如何重构二叉树呢？其实仔细想想，它和知道前序和中序来构造二叉树的原理是一样，只不过后序的根节点在序列的最后，只要知道根节点那么就可以去扫描中序序列，然后确定左子树和右子树，代码如下：
1 void rebuild_bitree(char *in_order,
2 char *post_order,
3 int treelen,
4 NODE **root) {
5 if (in_order == NULL ||
6 post_order == NULL ||
7 treelen <= 0) {
8 return;
9 }
10
11 if (*root == NULL) {
12 *root = new NODE;
13 }
14 (*root)->value = post_order[treelen - 1];
15 (*root)->left = (*root)->right = NULL;
16
17 int i = 0;
18 for (i = 0; i < treelen; ++i) {
19 if (in_order[i] == post_order[treelen - 1]) {
20 break;
21 }
22 }
23
24 rebuild_bitree(in_order,
25 post_order,
26 i,
27 &(*root)->left);
28 rebuild_bitree(in_order + i + 1,
29 post_order + i,
30 treelen - i - 1,
31 &(*root)->right);
32 }
上面写出的都是递归算法，因为递归本质上就是利用栈来操作，所以，如果要采用非递归算法来实现的话该如何做呢？现在还是以知道后序和中序，来重建二叉树，还是前面的例子：
中序：d b a e c f
后序：d b e f c a
1、还是先用一个栈保存后序中的节点在中序中的索引值，初始栈为空
2、对后序从后向前扫描，1）若栈为空，则该节点直接入栈；2）若当前节点在中序中的索引值大于栈顶节点在中序中的索引值，则可知该节点为栈顶节点的右孩子；3）只要当前节点在中序中的索引值小于栈顶 节点在中序节点中的索引值，就连续出栈，当前节点是最后一个出栈节点的左孩子；
这样程序如下：
1 void rebuild_bitree(char *in_order,
2 char *post_order,
3 int treelen,
4 NODE **root) {
5 if (in_order == NULL || post_order == NULL || treelen <= 0) {
6 return;
7 }
8 if (*root == NULL) {
9 *root = new NODE;
10 (*root)->value = post_order[treelen - 1];
11 (*root)->left = (*root)->right = NULL;
12 }
13 std::stack<int> index_stack;
14 std::stack<NODE *> node_stack;
15 int i;
16 int j;
17 NODE *tmp1;
18 NODE *tmp2;
19 for (i = treelen - 1; i >= 0; --i) {
20 if (i == treelen - 1) {
21 tmp1 = *root;
22 } else {
23 tmp1 = new NODE;
24 tmp1->value = post_order[i];
25 tmp1->left = tmp1->right = NULL;
26 }
27 for (j = 0; j < treelen; ++j) {
28 if (in_order[j] == post_order[i]) {
29 break;
30 }
31 }
32 if (index_stack.empty()) {
33 index_stack.push(j);
34 node_stack.push(tmp1);
35 } else if (j > index_stack.top()) {
36 node_stack.top()->right = tmp1;
37 index_stack.push(j);
38 node_stack.push(tmp1);
39 } else {
40 while (!index_stack.empty() && j < index_stack.top()) {
41 index_stack.pop();
42 tmp2 = node_stack.top();
43 node_stack.pop();
44 }
45 tmp2->left = tmp1;
46 index_stack.push(j);
47 node_stack.push(tmp1);
48 }
49 }
由前序和中序重构二叉树的非递归算法和上面相似，就是对前序由前向后扫描，具体算法就不写出来了
posted on 2012-09-03 14:24
myjfm 阅读(547)
评论(0) 编辑 收藏 引用 所属分类:
算法基础