由中序遍历和后序遍历重建二叉树，递归方式

由中序遍历和后序遍历重建二叉树，递归方式

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

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在JAVA中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目

本文永久更新链接地址：