二叉树的重建

系统管理员 2024-04-19 07:01 11阅读 0赞

### 文章目录 ###

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

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

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

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

代码如下:

#include <iostream>
    #include <string>
    #include <vector>
    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;
    }

输出结果:  
`a d b g c e f h`

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

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

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

代码如下:

#include <iostream>
    #include <string>
    #include <vector>
    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;
    }

输出结果:  
`g b d e h f c a`