由中序遍历和后序遍历重建二叉树,递归方式
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;
}