由前序遍历和中序遍历重建二叉树,递归方式

大数据分析BDA 2015-01-12

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

相关推荐