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

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