【www.bbyears.com--安卓教程】
已知某二叉树的前序遍历结果和中序遍历结果，假如前序遍历和中序遍历的结果中都不含重复的数字。例如某个二叉树的前序遍历的序列为{1,2,4,7,3,5,6,8}中序遍历序列{4,7,2,1,5,3,8,6}。
通过前序遍历和中序遍历重建二叉树
struct BinaryTreeNode{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
}
先把三种遍历算法写上：
// 前序遍历
void preOrder(BinaryTreeNode* binaryTreeNode){
if (binaryTreeNode != NULL)
{
printf("%d ",m_pLeft->m_nValue);
preOrder(binaryTreeNode->m_pLeft);
preOrder(binaryTreeNode->m_pRight);
}
}
// 中序遍历
void inOrder(BinaryTreeNode* binaryTreeNode){
if (binaryTreeNode != NULL)
{
inOrder(binaryTreeNode->m_pLeft);
printf("%d ",binaryTreeNode->m_nValue);
inOrder(binaryTreeNode->m_pRight);
}
}
// 后续遍历
void postOrder(BinaryTreeNode* binaryTreeNode){
if(binaryTreeNode != NULL)
{
postOrder(binaryTreeNode->m_pLeft);
postOrder(binaryTreeNode->m_pRight);
printf("%d ",m_pLeft->m_nValue);
}
}
主要还是利用递归，因为二叉树本身就是一种递归的产物，而且又是有序的，所以找到规律递推处理即可。根据上面的图应该可以分析出下面的代码：
BinaryTreeNode* ConstructCore(int* startPreorder,int* endPreorder,int* startInorder,int* endInorder){
// 前序遍历序列的第一个数字是根节点
int rootValue = startInorder[0];
BinaryTreeNode* root = new BinaryTreeNode();
root->m_nValue = rootValue;
root->m_pLeft = root->m_pRight = NULL;
// 在中序遍历中找到根节点
int* rootInorder = startInorder;
// 如果当前指针对应的指不是根节点，那么指针向后移动一次
while(rootInorder <= endInorder && *rootInorder != rootValue){
++ rootInorder;
}
int leftLength = rootInorder - startInorder;
int* leftPreorderEnd = startPreorder + leftLength;
if (leftLength > 0)
{
root->m_pLeft = ConstructCore(startPreorder + 1,leftPreorderEnd,startInorder,rootInorder - 1);
}
if (leftLength < endPreorder - startPreorder)
{
root->m_pRight = ConstructCore(leftPreorderEnd + 1,endPreorder,rootInorder + 1,endInorder);
}
return root;
}
加以完善，考虑周全些：
BinaryTreeNode* ConstructCore(int* startPreorder,int* endPreorder,int* startInorder,int* endInorder){
// 前序遍历序列的第一个数字是根节点
int rootValue = startInorder[0];
BinaryTreeNode* root = new BinaryTreeNode();
root->m_nValue = rootValue;
root->m_pLeft = root->m_pRight = NULL;
if (startPreorder == endPreorder)
{
if (startInorder == endInorder && *startPreorder == *startInorder)
{
return root;
}else{
throw std::exception("Invalid input.");
}
}
// 在中序遍历中找到根节点
int* rootInorder = startInorder;
// 如果当前指针对应的指不是根节点，那么指针向后移动一次
while(rootInorder <= endInorder && *rootInorder != rootValue){
++ rootInorder;
}
// 如果遍历完中序遍历的结果之后都没有找到和前序遍历结果相同的根节点
if (rootInorder == endInorder && *rootInorder != rootValue)
{
throw std::exception("Invalid input.");
}
int leftLength = rootInorder - startInorder;
int* leftPreorderEnd = startPreorder + leftLength;
if (leftLength > 0)
{
root->m_pLeft = ConstructCore(startPreorder + 1,leftPreorderEnd,startInorder,rootInorder - 1);
}
if (leftLength < endPreorder - startPreorder)
{
root->m_pRight = ConstructCore(leftPreorderEnd + 1,endPreorder,rootInorder + 1,endInorder);
}
return root;
}