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

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