二叉树重建[UVA-536]

二叉树重建Tree Recovery(UVA-536,ULM1997)

时间限制3000ms

分别是书上习题6-3，涉及到二叉树这一数据结构中已知两种遍历求整个树的过程。

首先需要复习一下二叉树的前序遍历和中序遍历和后序遍历。二叉树的前序遍历是指，先输出根结点的值，然后依次递归调用遍历左右子树；中序遍历是指，先递归遍历左子树，然后输出根结点的值，然后递归遍历右子树；后续遍历是指，先递归遍历左右子树，然后输出根结点的值。下面的解题分析都是以此为基础的。

以第一个样例输入为例：

先序遍历：DBACEGF

中序遍历：ABCDEFG

前面提到，前序遍历首先会输出当前子树的根结点，因此位于前序遍历的第一个元素D，一定是当前树的根。而在中序遍历中，根在中间输出，因而在中序遍历中查找根D，将整个中序遍历分为了两大部分：分别是树的左子树和右子树，如下所示

(ABC) (EFG)

那左右子树又该如何得到呢？很容易想到用递归的方法来构建，也就是利用了自顶向下的求解思路。左右子树的中序遍历很容易得到（利用找到的根的位置将其一分为二），而如何得到在原前序遍历中的子树呢？我们知道，前序遍历在输出根结点后，依次输出其左右的结点，所以关键的一步在于确定左右子树的结点个数。而利用之前中序遍历找到的根的位置，不难确定其个数。因此整个重建的算法就很明了了。剩下的问题就是如何确定递归出口。也很简单，只要输入时的数组只有一个元素，即对应的树没有孩子，那么该结点实际就是原树的一个叶子，递归也就结束了。整个过程的时间为$O(n^2)$。

我的的C++代码如下：（我的二叉树是按照《算法导论》一书中的描述定义的，包含了父节点。所以需要额外的处理一下。）

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 template<typename T>
 5 struct treenode
 6 {
 7     T value;
 8     treenode * leftchild;
 9     treenode * rightchild;
10     treenode * parent;
11     treenode()
12     {
13         value = 0; leftchild = rightchild = parent = nullptr;
14     }
15     treenode(int v) :value(v)
16     {
17         leftchild = rightchild = parent = nullptr;
18     }
19 };
20 template<typename T>
21 int search(T A[], T value, int size)
22 {
23     int i;
24     for (i = 0; i < size; i++)
25         if (A[i] == value)
26             return i;
27     return -1;
28 }
29 template<typename T>
30 treenode<T> * treerecovery(T inorder[], T postorder[], int size)
31 {
32     if (size == 1)
33         return new treenode<T>(inorder[0]);
34     int pos = search(inorder, postorder[0], size);
35     treenode<T> * ptleft = nullptr;
36     treenode<T> * ptright = nullptr;
37     treenode<T> * ptthis = new treenode<T>(postorder[0]);
38     if (pos != 0)
39     {
40 
41         ptleft = treerecovery(inorder, postorder + 1, pos);
42         ptleft->parent = ptthis;
43     }
44     if (pos != size - 1)
45     {
46         ptright = treerecovery(inorder + pos + 1, postorder + pos + 1, size - pos - 1);
47         ptright->parent = ptthis;
48     }
49     ptthis->leftchild = ptleft;
50     ptthis->rightchild = ptright;
51     return ptthis;
52 }
53 template<typename T>
54 void traversep(treenode<T> * tn)
55 {
56     if (tn == nullptr)
57         return;
58     treenode<T> * pt = tn;
59     traversep(tn->leftchild);
60     traversep(tn->rightchild);
61     std::cout << tn->value;
62 }
63 int main()
64 {
65 #define TMAX 30
66     char A[TMAX];
67     char B[TMAX];
68     while (std::cin >> A)
69     {
70         std::cin >> B;
71         int len = strlen(A);
72         treenode<char> * tree = treerecovery(B, A, len);
73         traversep(tree);
74         std::cout << std::endl;
75     }
76     return 0;
77 }

需要说明的是，必须要有中序遍历，才能够确定唯一的二叉树。换言之，只有前序和后序遍历是无法得到唯一确定的二叉树的。为什么呢？理由很简单，没有办法确定这个树左右节点是不是满的。以输入用例为例，只知道根节点D，剩余的元素，完全可以作为单纯的左子树或者右子树，也可以作为两支。