ntf("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 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
找不到