由中序遍历和后序遍历重建二叉树，递归方式

1、二叉树定义typedef struct BTreeNodeElement_t_ {
void *data;
} BTreeNodeElement_t;
typedef struct BTreeNode_t_ {
BTreeNodeElement_t *m_pElemt;
struct BTreeNode_t_ *m_pLeft;
struct BTreeNode_t_ *m_pRight;
} BTreeNode_t;2、由中序遍历和后序遍历重建二叉树中序遍历中，根节点总是位于左右子树中间，将左右子树分开。后序遍历中，根节点总是在左右子树之后。重建算法：现在说一下重建根节点的过程，其他节点可以递归建立。由后序遍历定义可知，后序遍历序列的最后一个元素必定是整个树的根节点，这样就确定了根节点。由中序遍历定义可知，在中序遍历中查找根节点，可以确定根节点在中序遍历序列中位置，这样就可以将中序遍历序列分为左右子树，一旦确定左右子树，左右子树的长度也就确定了，根据左右子树的长度，在后序遍历序列中，可以确定左右子树的根节点，这样递归下去既可以确定整个树。BTreeNode_t *RebuildBTree（ const BTreeNodeElement_t *pInorder,
const BTreeNodeElement_t *pPostorder,
const int nodesTotal,
int （*compare）（const BTreeNodeElement_t*, const BTreeNodeElement_t*）
）{
if（ pInorder == NULL || pPostorder == NULL || nodesTotal <= 0 || compare == NULL ）
return NULL; BTreeNode_t *pRoot= new BTreenode_t;
if（ pRoot == NULL ）
return NULL; BTreeNodeElement_t *pElemt= &pPostorder[ nodesTotal - 1 ];//后序遍历序列的最后一个值是根节点
pRoot->m_pElemt = pElemt;

int rootIndexInorder = -1;
for（ int i = 0 ; i < nodesTotal; ++i）{
if（ compare（ pElemt, &pInorder[i]） == 0 ）{//在中序遍历序列中找到根节点，确定根节点的索引
rootIndexInorder = i;
break;
}
} if（ rootIndexInorder == -1 ）
return NULL; int leftNodesTotal = rootIndexInorder;//由根节点索引可以确定左右子树的长度，因为中序遍历根节点作为左右子树的分隔点
BTreeNodeElement_t *pLeftPostorder = pPostorder;
BTreeNodeElement_t *pLeftInorder = pInorder;
pRoot->m_pLeft = RebuildBTree（ pLeftInorder,
pPostorder,
leftNodesTotal,
compare
）; int rightNodesTotal = nodesTotal - leftNodesTotal - 1;
BTreeNodeElement_t *pRightPostorder = pPostorder + leftNodesTotal;//确定了左右子树的长度，也就确定了左右子树序列的起始位置
BTreeNodeElement_t *pRightInorder = pInorder + leftNodesTotal + 1;
pRoot->m_pRight = RebuildBTree（ pRightInorder,
pRightPostorder,
rightNodesTotal,
compare
）; return pRoot;
}二叉树的常见问题及其解决程序 http://www.linuxidc.com/Linux/2013-04/83661.htm【递归】二叉树的先序建立及遍历 http://www.linuxidc.com/Linux/2012-12/75608.htm在JAVA中实现的二叉树结构 http://www.linuxidc.com/Linux/2008-12/17690.htm【非递归】二叉树的建立及遍历 http://www.linuxidc.com/Linux/2012-12/75607.htm二叉树递归实现与二重指针 http://www.linuxidc.com/Linux/2013-07/87373.htm二叉树先序中序非递归算法 http://www.linuxidc.com/Linux/2014-06/102935.htm轻松搞定面试中的二叉树题目 http://www.linuxidc.com/linux/2014-07/104857.htm本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-01/111632.htm