假設已經有了前序遍歷和中序遍歷的結果，希望通過一個算法重建這棵樹。已知遍歷結果為字符串，且樹的每個節點的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 閱讀(574)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎