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;
}