二叉树（14）----由前序遍历和中序遍历重建二叉树，递归方式

水深无声 2022-03-31 13:43 147阅读 0赞

相关链接：

[链表总结----链表面试题合集][----]

[二叉树----二叉树面试题合集 ][----_]

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://blog.csdn.net/beitiandijun/article/details/41917111
[----_]: http://blog.csdn.net/beitiandijun/article/details/42030399