二叉树的遍历转换（层序，中序转先序）

　　众所周知二叉树有四种遍历，即先序（DLR），中序（LDR），后序（LRD）和层序。而层序和其它三种不同，因为它是用的BFS即广度优先搜索。我们可以简单证明中序遍历和其它的任何一种遍历可以确定一棵树。常见的有已知先序中序求后序，已知中序后序求先序（比如noip2001PJ的那道水题）。还有一种不常见的有层序中序求先后序。

　　前面两种太水，递归二分很容易做，后面一种做的时候没反应过来想了会儿，本来想用递归，但是如果用递归的话一会儿二分左子树一会儿二分右子树，不方便，所以我改用队列做。

　　我们用一个队列来储存当前要二分的中序遍历，先将一开始的完整的中序遍历加进去。

　　然后查找当前要处理的中序遍历，将他二分，将左右两部分分别加入队列。再如此处理二分的两部分队列。

　　重复这些操作，直至队列为空（或者说是层序遍历查找完毕），下面是主要部分的源代码;

void make_tree(string str1,string str2,queue <string> que){
    que.push(str1);
    int now=1;
    for(int i = 0; i < str2.length(); i++) {
		char &k = str2[i];
		string &s = que.front();
		string left,right;
		int j;
		for(j = 0; j < s.length(); j++) {
			if(s[j] == k) {
				tree[now] = k;
				for(int l = j + 1; l < s.length(); l++)
					right = right + s[l];
				que.push(left);
				que.push(right);
				que.pop();
				break;
			}
			else
				left = left + s[j];
		}
		now++;
		if(j == s.length()) {                   //如果能在s中找到k，则j必定小于lens，而找不到的情况只可能出现在该子树大小为0的情况
			i--;
			que.push(left);                 //加入一个大小为0的树的中序遍历，防止now不按顺序来，下同
			que.push(right);
			que.pop();
		}
	}
}

　　观察上面的源代码，可以发现，我们是将整棵树补齐了，也就是说最坏的情况就是如下图：

其中空心圆表示无结点，实心圆表示结点。

对于N个结点（如图），时间复杂度上界为O(2^n · n^2);（应该没算错吧？？）

如果没算错，那么这样只能最多处理n=19的情况，过大的会超时，那我们该怎么优化这个呢？

首先为什么我们会执行2^n次操作呢？是因为我们如果不存2^n次则无法将每个结点对号入座。

那么我们可不可以用一个队列来存储结点应该做哪个位置呢？答案是可以的。

下面是代码：

#include<iostream>
#include<queue>
#include<string>
#include<sstream>
#include<cstring>
using std::cin;
using std::string;
using std::queue;
char tree[10000 + 20];
int first(int);

int main(){
    string str1;    //中序
    cin >> str1;
    string str2;    //层序
    cin >> str2;
    queue <string> que;
    queue <int> place; 
    que.push(str1);
    place.push(1);
    for(int i = 0; i <= 10000 + 19; i++)
        tree[i] = '#';
    for(int i = 0; i < str2.length(); i++) {
        char &k = str2[i];
        string &s = que.front();
        string left,right;
        int j;
        for(j = 0; j < s.length(); j++) {
            if(s[j] == k) {
                tree[place.front()] = k;
                for(int l = j + 1; l < s.length(); l++)
                    right = right + s[l];
                if(left.empty() == false) {
                    que.push(left);
                    place.push(place.front() * 2);
                }
                if(right.empty() == false) {
                    que.push(right);
                    place.push(place.front() * 2 + 1);
                }
                que.pop();
                break;
            }
            else
                left = left + s[j];
        }
        place.pop();
    }
    first(1);
    return 0;
} 

int first(int x) {
    printf("%c" , tree[x]);
    if(tree[x * 2] != '#') {
        first(x * 2);
    }
    if(tree[x * 2 + 1] != '#') {
        first(x * 2 + 1);
    }
}

主要的改变就是用了一个place队列保存下一个元素要出现的位置，这样就用空间换时间

这段代码的时间复杂度为O(n^3)?数学没学好算不出来，总之就是快了好多好多。

二叉树的遍历转换（层序，中序转先序）

推荐阅读