本文共 2541 字，大约阅读时间需要 8 分钟。

1.根据二叉树的中序和后续遍历重建二叉树

思路：假设递归过程中，某一步的后序序列区间为[postL,postR]，中序序列区间为[inL,inR]；

1. 根据后序遍历的特点可知，postR位置为根结点；2. 从中序序列中，寻找出root的位置k，k左边的均为左子树，右边的均为右子树；3. 将左子树区间[postL,k-1]作为新的后序和中序序列，进行递归。

代码如下:

#include 
   
    #include 
    
     #include 
     
      using namespace std;struct BTNode {
   	BTNode(char data):_data(data),_pLeft(nullptr),_pRight(nullptr){
   }	char _data;	BTNode* _pLeft;	BTNode* _pRight;};void PreOrder(BTNode* pRoot) {
   	if (pRoot == nullptr)		return;	cout << pRoot->_data << " ";	PreOrder(pRoot->_pLeft);	PreOrder(pRoot->_pRight);}void PostOrder(BTNode* pRoot) {
   	if (pRoot == nullptr)		return;	PostOrder(pRoot->_pLeft);	PostOrder(pRoot->_pRight);	cout << pRoot->_data << " ";}BTNode* ReBuildBTTree(string& Post, string& In, int PostL, int PostR, int InL, int InR) {
   	if (PostL > PostR)		return nullptr;	BTNode* pRoot = new BTNode(Post[PostR]);	int k = 0;	while (In[k] != pRoot->_data) {
   		++k;	}	int numLeft = k - InL;	pRoot->_pLeft = ReBuildBTTree(Post, In, PostL, PostL + numLeft - 1, InL, k - 1);	pRoot->_pRight = ReBuildBTTree(Post, In, PostL + numLeft, PostR - 1, k + 1, InR);	return pRoot;}int main() {
   	string In = "dgbaechf";	string Post = "gbdehfca";	string Pre = "adbgcefh";	BTNode* pNewRoot = ReBuildBTTree(Post, In, 0, 7, 0, 7);	PreOrder(pNewRoot);	cout << endl;	system("pause");	return 0;}
     
    
   

输出结果:

2.根据二叉树的中序和前序遍历重建二叉树

思路：假设递归过程中，某一步的后序序列区间为[preL,preR]，中序序列区间为[inL,inR]；

1. 根据前序遍历的特点可知，postL位置为根结点；2. 从中序序列中，寻找出root的位置k，k左边的均为左子树，右边的均为右子树；3. 将左子树区间[preL+1,preL+numLeft]作为新的后序和中序序列，进行递归。

代码如下:

#include 
   
    #include 
    
     #include 
     
      using namespace std;struct BTNode {
   	BTNode(char data):_data(data),_pLeft(nullptr),_pRight(nullptr){
   }	char _data;	BTNode* _pLeft;	BTNode* _pRight;};void PostOrder(BTNode* pRoot) {
   	if (pRoot == nullptr)		return;	PostOrder(pRoot->_pLeft);	PostOrder(pRoot->_pRight);	cout << pRoot->_data << " ";}BTNode* Create(string& Pre, string& In, int preL, int preR, int InL, int InR) {
   	if (preL > preR)		return nullptr;	BTNode* pRoot = new BTNode(Pre[preL]);	int k = 0;	while (In[k] != pRoot->_data) {
   		++k;	}	int numLeft = k - InL;	pRoot->_pLeft = Create(Pre, In, preL + 1, preL + numLeft, InL, k - 1);	pRoot->_pRight = Create(Pre, In, preL + numLeft + 1, preR, k + 1, InR);	return pRoot;}int main() {
   	string In = "dgbaechf";	string Post = "gbdehfca";	string Pre = "adbgcefh";	BTNode* pNew2 = Create(Pre, In, 0, 7, 0, 7);	PostOrder(pNew2);	cout << endl;	system("pause");	return 0;}
     
    
   

输出结果:

转载地址：https://blog.csdn.net/a_hang_szz/article/details/100848140 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！