根据前序和中序遍历结果重建二叉树

前序遍历： 根节点—->左子树—->右子树 中序遍历： 左孩子—->根节点—->右子树 根据前序遍历的特性可以得知： 1.前序遍历后的第一个节点就是这棵树的根节点。 2.根据中序遍历找到根节点后，其左边的节点都是根节点的左子树，其右边的节点都是根节点的右子树。 3.用递归的方式将根节点的左子树和右子树分别看成是一棵树。 对于递归出口，可以是：beginPre = endPre beginPre：先序遍历的第一个节点的值 endPre：先序遍历的最后一个节点的值 beginIn:中序遍历的第一个节点的值 endIn：中序遍历的最后一个节点的值 可以将这四个值作为函数的参数列表来传递。

创建树的结点：

#include <iostream> #include <windows.h> #include <stdlib.h> using namespace std; struct Node { int _value; Node* _pLeft; Node* _pRight; };

递归创建树:

Node* PreAndInOrderBuilt(int arrPre[], size_t beginPre,size_t endPre, int arrIn[], size_t beginIn,size_t endIn) { if(endPre-beginPre != endIn-beginIn) { cout<<"先序遍历与中序遍历长度不相等。。。"<<endl; return NULL; } if(beginPre > endPre) return NULL; Node* pRoot = (Node*)malloc(sizeof(Node));//创建根节点 pRoot->_value = arrPre[beginPre]; pRoot->_pLeft = NULL; pRoot->_pRight = NULL; if(beginPre == endPre) return pRoot; //在中序遍历中找到跟结点的位置，区分开左子树与右子树 size_t index = beginIn; for(index; index<=endIn; index++) { if(arrIn[index] == arrPre[beginPre]) break; } if(index > endIn)//两个数的根节点不同 return NULL; //创建左子树 size_t newendPre = 0; if(index > beginIn)//左子树存在 { newendPre = beginPre + (index-beginIn); pRoot->_pLeft = PreAndInOrderBuilt(arrPre, beginPre+1,newendPre, arrIn, beginIn, index-1); } //创建右子树 if(index < endIn)//右子树存在 { pRoot->_pRight = PreAndInOrderBuilt(arrPre, beginPre+index+1,endPre, arrIn, index+1, endIn); } return pRoot; }

调用：

int main() { int preOrder[] = {1,2,4,5,3,6}; int inOrder[] = {4,2,5,1,6,3}; Node* tree = PreAndInOrderBuilt(preOrder,0,5,inOrder,0,5); system("pause"); return 0; }