由前序遍歷和中序遍歷重建二叉樹，遞歸方式

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;

二、根據前序遍歷序列和中序遍歷序列重建二叉樹

算法說明：

由中序遍歷序列可知，第一個節點是根節點，

由前序遍歷序列可知，第一個節點是根節點的左子樹節點，而且前序遍歷中，根節點左邊是左子樹，右邊是右子樹，因此通過中序遍歷的根節點可以確定的是：

根節點在前序遍歷中的位置（通過遍歷前序遍歷序列，比較每一個節點與中序遍歷中的第一個節點即根節點可知）；

左子樹的節點數，因為一旦找到前序遍歷中根節點的位置，就找到左右子樹的分界點，也就是說，前序遍歷中根節點左邊的都是左子樹節點，可以通過遍歷知道左子樹的節點數；

同樣，右子樹的節點數也可以確定。

通過以上確定的信息，可以劃分出前序遍歷中的左右子樹節點數，根節點位置；因此，下面就是進行求根節點左節點和右節點，而根據上述劃分，可以知道左子樹前序和中序序列起始位置以及長度、右子樹前序和中序序列起始位置以及長度，這樣可以遞歸按照上述方式同樣獲得左右子樹的根節點。

通過遞歸可以求得整個樹的結構。

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

二叉樹的常見問題及其解決程序 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