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;
二、根据前序遍历序列和中序遍历序列重建二叉树
算法说明：
由中序遍历序列可知，第一个节点是根节点，
由前序遍历序列可知，第一个节点是根节点的左子树节点，而且前序遍历中，根节点左边是左子树，右边是右子树，因此通过中序遍历的根节点可以确定的是：
根节点在前序遍历中的位置（通过遍历前序遍历序列，比较每一个节点与中序遍历中的第一个节点即根节点可知）；
左子树的节点数，因为一旦找到前序遍历中根节点的位置，就找到左右子树的分界点，也就是说，前序遍历中根节点左边的都是左子树节点，可以通过遍历知道左子树的节点数；
同样，右子树的节点数也可以确定。
通过以上确定的信息，可以划分出前序遍历中的左右子树节点数，根节点位置；因此，下面就是进行求根节点左节点和右节点，而根据上述划分，可以知道左子树前序和中序序列起始位置以及长度、右子树前序和中序序列起始位置以及长度，这样可以递归按照上述方式同样获得左右子树的根节点。
通过递归可以求得整个树的结构。
BTreeNode_t * RebuildBTree( const BTreeNodeElement_t *pPreorder,
const BTreeNodeElement_t *pInorder,
const int nodesTotal,
int(*compare)(const BTreeNodeElement_t*, const BTreeNodeElement_t *)){
if( pPreoder == NULL || pInorder == NULL || nodesTotal <= 0 || compare == NULL)
return NULL;
BTreeNodeElement_t *pRootData = &pInorder[0]; //找到当前树的根节点
BTreeNode_t *pRoot= new BTreeNode_t;
pRoot->m_pElemt = pRootData;
int rootIndex = -1;
for( int i = 0; i < nodesTotal; ++i){
if( compare( pRootData, &pPreorder[i]) == 0){
rootIndex = i;
brea;
}
}
if( rootIndex == -1 )
return NULL;
//根据查找到根节点得到的信息，左子树长度，右子树长度等
int leftNodesTotal = rootIndex;
BTreeNodeElement_t *pLeftPreorder = pPreorder + 1;
BTreeNodeElement_t *pLeftInorder = pInorder;
pRoot->m_pLeft = RebuildBTree( pLeftPreorder, pInorder, leftNodesTotal, compare);
//右子树信息
int rightNodesTotal = nodesTotal - leftNodesTotal - 1;//减去右子树节点数和一个根节点
BTreeNodeElement_t *pRightPreOrder = pPreorder + leftNodesTotal + 1;
BTreeNodeElement_t *pRightInorder = pInorder + leftNodesTotal + 1;
pRoot->m_pRight = RebuildBTree( pRightPreOrder, pRightInorder, rightNodesTotal, compare);
return pRoot;
}
在Java中实现的二叉树结构