关于二叉树-创新互联

在已知中序的前提下，任意知道前序或后序皆可得到唯一的二叉树

假若一个中序序列为：ABEDFCHG

又知前序序列为：CBADEFGH

由于前序序列是按照根左右来进行遍历的

所以前序序列的第一个一定是二叉树的根结点！

即：

然后中序序列是按照左根右来进行遍历的

所以中序序列的根一定将左右子树进行了分离

先不管ABEDF哪个是根，反正他们都是作为C的左子树的一个结点

HG则作为C的右子树

即：

接下来前序序列的下一个又是一个子根，所以重复前面的操作得到：

接下来在中序中A的左右已经没有更后的结点了也就说明它没有左右子树(属于叶子结点)

在中序中(ABEDFCHG), A的左边没有元素，A的右边是B，但是B是在前面的，
所以B不会作为A的子树，故A的左右都没有元素，得出A是叶子结点的结论

最终成图：

首先假若有一个中序序列为：ABEDFCHG

又知前序序列为：CBADEFGH

那么我们先分析后序遍历的需求，后序是根据左右根来遍历的

所以我们先要找根的左子树结点，再根据左子树结点找其左子树结点，直到左子树结点为空

然后再找返回去根节点找其右子树，重复上述内容(找右子树的左子树)

所以根据我们的分析得出，这个题可以使用递归来解决

递归思想：把规模大的、较难解决的问题变成规模小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。
三个使用条件：
1、可以将一个大问题转为小问题
2、可以通过转化过程使得问题得到解决
3、有一个明确的结束递归的条件

根据上图我们可以写出代码

首先找出根节点(第一个根节点是C)

然后左子树是：ABEDF，右子树为HG

然后再根据左子树中找到根节点B(通过中序的下一位来判断)

我们可以每记录了一次根节点之后可以将对应的根节点清除，这样后面就不用特别处理了
这里提供一种清除方法
清除前序遍历的根节点：tpreor.erase(tpreor.begin());
清除中序遍历的根节点：tinfor.erase(temp, 1);
( temp 为 tinfor.find(root) -->root为每一次的根节点 root = tpreor[0]);
又或者可以利用下标来进行操作，只不过使用清除的方法更加明显实质一点
利用下标的话就不用进行清除了，每次只需要改变下标即可

然后在遍历左子树来重复前面的操作

直到左子树都执行结束后再对右子树进行同样的操作

具体实现为：
traversal(left_tpreor, left_tinfor);
traversal(right_tpreor, right_tinfor);
若左右子树都遍历结束后再进行输出根节点
cout<< root; //因为是后序遍历(只有左子树和右子树到头了再输出根结点)

完整代码：

#include#includeusing namespace std;

string preor, infor;
//前序后序 
void traversal(string tpreor, string tinfor){
	
	if(tinfor.empty()) return;	//这时候中序的元素都找完了，就可以返回程序了
	char root = tpreor[0]; //取根节点
	int temp = tinfor.find(root);	//从中序中找根结点
	tpreor.erase(tpreor.begin());	//清除前序最前面的字符
	tinfor.erase(temp, 1);	//清除中序的根结点
	string left_tpreor = tpreor.substr(0, temp);	//记录左子树
	string left_tinfor = tinfor.substr(0, temp);
	string right_tpreor = tpreor.substr(temp);	//记录右子树
	string right_tinfor = tinfor.substr(temp);
	
	traversal(left_tpreor, left_tinfor);	//操作左子树
	traversal(right_tpreor, right_tinfor);	//操作右子树
	cout<< root;	//左子树和右子树都遍历完了后就可以输出了
	
}

int main()
{
	
	cin >>infor >>preor;
	
	traversal(preor, infor);
	
	return 0;
}

未完待续…

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧