stack <BTreeNode_t *> st1;
stack <BTreeNode_t *> st2;
int flag = 0;
while( (pRoot1 != NULL || !st1.empty()) &&
( pRoot2 != NULL || !st2.empty()) ){
while( pRoot1 != NULL && pRoot2 != NULL){
printf("note: cur data: pRoot1->m_nValue: %d, pRoot2->m_nValue: %d\n",
pRoot1->m_nValue, pRoot2->m_nValue);
if( pRoot1->m_nValue != pRoot2->m_nValue){
flag = -1;
break;
}
st1.push( pRoot1);
st2.push( pRoot2);
pRoot1 = pRoot1->m_pLeft;
pRoot2 = pRoot2->m_pLeft;
}
if( flag != 0 )
break;
if( !st1.empty() && !st2.empty()){
pRoot1 = st1.top();
st1.pop();
pRoot2 = st2.top();
st2.pop();
pRoot1 = pRoot1->m_pRight;
pRoot2 = pRoot2->m_pRight;
}
}
if( pRoot2 != NULL || !st2.empty() ){
flag = -1;
}
while( !st1.empty() ){
st1.pop();
}
while( !st2.empty() ){
st2.pop();
}
return flag;
}
int check_is_include( BTreeNode_t *pRoot1, BTreeNode_t *pRoot2){
if( pRoot1 == NULL || pRoot2 == NULL ){
fprintf(stderr, "ERROR: in check_is_include(), input param error\n");
return INPUT_PARAM_ERROR;
}
stack <BTreeNode_t*> st;
int flag = -1;
while( pRoot1 != NULL || !st.empty()){
while( pRoot1 != NULL){
printf("note: now check node data: %d\n", pRoot1->m_nValue);
if( check_is_include_helper( pRoot1, pRoot2) == 0 ){
flag = 0;
break;
}
st.push( pRoot1);
pRoot1 = pRoot1->m_pLeft;
}
if( flag == 0)
break;
if( !st.empty() ){
pRoot1 = st.top();
st.pop();
pRoot1 = pRoot1->m_pRight;
}
}
while( !st.empty() )
st.pop();
return flag;
}
int
main( int argc, char ** argv){
if( argc < 3 ){
fprintf(stderr, "ERROR: file(%s), line(%d), input parameter error\n", __FILE__, __LINE__);
return INPUT_PARAM_ERROR;
}
char *afile = argv[1];
char *bfile = argv[2];
int ret = 0;
int *pPreOrder = NULL;
int *pInOrder = NULL;
BTreeNode_t *pRoot1 = NULL;
BTreeNode_t *pRoot2 = NULL;
int tree_nodes_total = 0;
ret = get_traverse_nodes( afile, &pPreOrder, &pInOrder, &tree_nodes_total);
if( ret != 0 || tree_nodes_total == 0){
fprintf(stderr, "ERROR: failure to get tree nodes info from file(%s)\n", afile);
goto end;
}
pRoot1 = reconstruct_btree_by_preinorder( pPreOrder, pInOrder, tree_nodes_total);
if( pRoot1 == NULL ){
fprintf(stderr, "ERROR: failure to rebuild btree from file(%s)\n", afile);
ret = REBUILD_BTREE_ERROR;
goto end;
}
free( pPreOrder );
pPreOrder = NULL;
free( pInOrder );
pInOrder = NULL;
print_btree( pRoot1 );
ret = get_traverse_nodes( bfile, &pPreOrder, &pInOrder, &tree_nodes_total);
if( ret != 0 || tree_nodes_total == 0){
fprintf(stderr, "ERROR: failure to get tree nodes info from file(%s)\n", bfile);
goto end;
}
pRoot2 = reconstruct_btree_by_preinorder( pPreOrder, pInOrder, tree_nodes_total);
if( pRoot2 == NULL ){
fprintf(stderr, "ERROR: failure to rebuild btree from file(%s)\n", bfile);
ret = REBUILD_BTREE_ERROR;
goto end;
}
print_btree( pRoot2);
#if 1
ret = check_is_include( pRoot1, pRoot2);
if( ret != 0 ){
fprintf(stderr, "ERROR: failure to find b btree in a btree\n");
goto end;
}
#endif
printf("NOTE: success to find b btree in a btree\n");
end:
if( pPreOrder != NULL ){
free(pPreOrder);
pPreOrder = NULL;
}
if( pInOrder != NULL ){
free( pInOrder );
pInOrder = NULL;
}
if( pRoot1 )
release_btree( pRoot1);
if( pRoot2 )
release_btree( pRoot2);
return ret;
}
代码运行显示：
二叉树A：
1
2 3
4 5 6 7
8
二叉树B：
3
6 7
分别存放在aBTree.txt和bBTree.txt中
aBTree.txt：
bBTree.txt：
运行：
./a.out aBTree.txt bBTree.txt
可以找到
./a.out aBTree.txt aBTree.txt
找不到