一個二叉樹是否包含另一個二叉樹

1、問題描述

二叉樹A和B的每個節點的數據（int型數據）存儲在不同文件中，存儲方式為前序遍歷和中序遍歷，根據這兩種遍歷重建二叉樹，並且判斷二叉樹A是否包含二叉樹B。

1、算法描述

（1）首先將節點數據的前序遍歷和中序遍歷序列讀入數組

（2）分別根據各自的前序遍歷和中序遍歷重建二叉樹A和B

（3）判斷B是否在A中

代碼：

#include <stdio.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <string.h>
#include <stdlib.h>
#include <memory.h>
#include <stack>

using namespace std;

enum COMMON_SIZE
{
 BUF_MAX_SIZE = 1024,
 MAX_NUM_LEN = 10,
};

enum ERROR_VALUE
{
 INPUT_PARAM_ERROR = -1,
 OPEN_FILE_ERROR = -2,
 FILE_NOT_EXSIT = -3,
 FILE_IS_EMTPY = -4,
 ALLOCA_FAILURE = -5,
 REBUILD_BTREE_ERROR = -6,
 NUM_OVERFLOW_ERROR = -7,
};

typedef struct BTreeNode_t_{
 int m_nValue;
 struct BTreeNode_t_ *m_pLeft;
 struct BTreeNode_t_ *m_pRight;
} BTreeNode_t;

void release_btree( BTreeNode_t *pRoot){
 if( pRoot == NULL )
  return;

 if( pRoot->m_pLeft )
  release_btree( pRoot->m_pLeft);
 if( pRoot->m_pRight)
  release_btree( pRoot->m_pRight);

 free(pRoot);
 pRoot = NULL;
 return;
}

BTreeNode_t * reconstruct_btree_by_preinorder( int *pPreOrder, int *pInOrder, int tree_nodes_total){
 if( pPreOrder == NULL || pInOrder == NULL ){
  fprintf(stderr, "ERROR: while construct btree by preinorder\n");
  return NULL;
 } 
 

 int m_nValue = pPreOrder[0];
 int root_data_index = -1;
 int i = 0;
 for( i = 0; i < tree_nodes_total; ++i ){
  if( pPreOrder[0] == pInOrder[i] ){
   root_data_index = i;
   break;
  }
 }

 if( root_data_index == -1 ){
  fprintf(stderr, "note: pPreOrder[0] is %d, pInOrder[0] is %d\n",
   pPreOrder[0], pInOrder[0]);
  fprintf(stderr, "note: root_data_index is -1, total nodes: %d\n", tree_nodes_total);
  return NULL;
 }

 BTreeNode_t *pRoot = NULL;
 pRoot = (BTreeNode_t *) malloc( sizeof( BTreeNode_t ));
 if( pRoot == NULL ){
  fprintf(stderr, "ERROR: can't alloca btree node: %d\n", m_nValue);
  return NULL;
 }

 pRoot->m_nValue = m_nValue;
 pRoot->m_pLeft = NULL;
 pRoot->m_pRight = NULL;

 int left_tree_len = root_data_index;
 int right_tree_len = tree_nodes_total - left_tree_len - 1;
 int *pleft_preorder = pPreOrder + 1;
 int *pright_preorder = pPreOrder + 1 + left_tree_len;
 int *pleft_inorder = pInOrder;
 int *pright_inorder = pInOrder + left_tree_len + 1;

 if( left_tree_len > 0 )
 {
  pRoot->m_pLeft = reconstruct_btree_by_preinorder( pleft_preorder, pleft_inorder, left_tree_len);
  if( pRoot->m_pLeft == NULL ){
   fprintf(stderr, "ERROR: failure to rebuild leftree, now release data: %d\n",
    m_nValue);
   release_btree( pRoot);
   pRoot = NULL;
   return NULL;
  }
 }

 if( right_tree_len > 0 ){
  pRoot->m_pRight = reconstruct_btree_by_preinorder( pright_preorder, pright_inorder, right_tree_len );
  if( pRoot->m_pRight == NULL ){
   fprintf(stderr, "ERROR: failure to right tree, now release data: %d\n",
    m_nValue);
   release_btree( pRoot );
   pRoot = NULL;
   return NULL;
  }
 }

 return pRoot;
}

int get_traver_data( char *buf, int *pOrder, int *order_len ){
 if( buf == NULL || pOrder == NULL ){
  return INPUT_PARAM_ERROR;
 }

 char *ptr = buf;
 char *pNumStart = ptr;
 int i = 0;
 int numLen = 0;
 int get_no_num = 0;
 int flag = 0;
 fprintf(stderr, "note: now enter get_traver_data()\n");
 while( *ptr != '\0' ){
  if( ( *ptr >= '0' ) && ( *ptr <= '9') ){
   ++numLen;
  } else  if( *ptr == ' ' ){
   *ptr = '\0';
   if( numLen > 0 && numLen <= MAX_NUM_LEN ){
    pOrder[i] = atoi( ptr - numLen );
    fprintf(stderr, "note: num is: %d\n", pOrder[i]);
    ++i; 
   }
   else if ( numLen > MAX_NUM_LEN){
    flag = NUM_OVERFLOW_ERROR;
    break;
   }
   numLen = 0;
   
  } else{
   get_no_num = -1;
   break;
  }

  ++ptr;
 }
 if( numLen != 0 ){
  pOrder[i] = atoi( ptr - numLen);
  fprintf(stderr, "note: num is: %d\n", pOrder[i]);
 }

 if( get_no_num != 0 )
  return get_no_num;

 *order_len = i + 1;
 fprintf(stderr, "note: finish get_traver_data()\n");
 return flag;
}

int get_traverse_nodes( char * file_name, int **pPreOrder, int **pInOrder, int *tree_nodes_total ){
 if( file_name == NULL ){
  fprintf(stderr, "ERROR: file(%s), line(%d), input parameter error\n",
    __FILE__, __LINE__);
  return INPUT_PARAM_ERROR; 
 }

 if( access( file_name, F_OK ) != 0){
  fprintf(stderr, "ERROR: file(%s) not exsit\n", file_name);
  return FILE_NOT_EXSIT;
 }

 struct stat fstat;
 size_t file_size = -1;

 stat(file_name, &fstat);
 file_size = fstat.st_size;
 if( file_size == 0 ){
  fprintf(stderr, "ERROR: file(%s) is empty\n", file_name);
  return FILE_IS_EMTPY;
 }
 fprintf(stderr, "note: file size: %ld\n", fstat.st_size);

 char * buf = NULL;
 buf = (char *)malloc( (file_size + 1) * sizeof( char ));
 if( buf == NULL ){
  fprintf(stderr, "ERROR: alloca buffer failure\n");
  return ALLOCA_FAILURE;
 }

 FILE *input = fopen( file_name, "rb");
 if( input == NULL ){
  fprintf(stderr, "ERROR: can't open input file [%s]\n", file_name);
  free(buf);
  buf = NULL;
  return OPEN_FILE_ERROR;
 }

 int line_len = -1;
 int index = 0;
 int flag = 0;
 int fini_read = 0;
 int preorder_len = 0;
 int inorder_len = 0;
 while( fgets( buf, file_size , input) != NULL ){
  size_t buf_len = strlen( buf );
  if( buf[ buf_len - 1] == '\n' )
   buf[ buf_len - 1 ] = '\0';
  fprintf(stderr, "note: current line is: %s\n", buf);
  switch( index )
  {
   case 0 :
   {
    *pPreOrder = (int *) malloc( buf_len * sizeof( int ));
    if( *pPreOrder == NULL ){
     flag = -1;
     break;
    }
    fprintf(stderr, "note: finish to get pPreOrder\n");
    flag = get_traver_data( buf, *pPreOrder, &preorder_len);
    break; 
   }
   case 1 :
   {
    *pInOrder = (int *) malloc( buf_len * sizeof( int ));
    if( *pInOrder == NULL ){
     flag = -1;
     break;
    }
    fprintf(stderr, "note: finish to get pInOrder\n");
    flag = get_traver_data( buf, *pInOrder, &inorder_len );
    break;
   }
   default:
   {
    break;
   }
  }

  ++index;
  if( flag != 0 || index == 2)
   break;
 }
 if( (flag != 0 ) || ( preorder_len != inorder_len)){
  fprintf(stderr, "ERROR: flag is %d, preorder_len is %d, inorder_len is %d\n", flag, preorder_len, inorder_len);
  if( *pPreOrder ){
   free( *pPreOrder );
   *pPreOrder = NULL;
  }
  if( *pInOrder ){
   free( *pInOrder );
   *pInOrder = NULL;
  }
  flag = -1;
 }

 free( buf );
 buf == NULL;

 fclose( input );
 input = NULL;

 *tree_nodes_total = preorder_len;
 fprintf(stderr, "note: sucess finish get_traverse_nodes()\n");
 return flag; 
}

void print_btree( BTreeNode_t *pRoot){
 if( pRoot == NULL )
  return;
 stack< BTreeNode_t *> st;
 while( pRoot != NULL || !st.empty()){
  while( pRoot != NULL ){
   printf("preorder test: node data: %d\n", pRoot->m_nValue);
   st.push( pRoot);
   pRoot = pRoot->m_pLeft;
  }
 
  if( !st.empty()){
   pRoot = st.top();
   st.pop();
   pRoot = pRoot->m_pRight;
  }
 }

 return;
}

void pprint_btree( BTreeNode_t *pRoot){
 if( pRoot == NULL )
  return;

 fprintf(stderr, "preorder test: node: %d\n", pRoot->m_nValue);
 if( pRoot->m_pLeft )
  print_btree( pRoot->m_pLeft);
 if( pRoot->m_pRight)
  print_btree( pRoot->m_pRight);

 return;
}

int check_is_include_helper( BTreeNode_t *pRoot1, BTreeNode_t *pRoot2){
 if( pRoot1 == NULL || pRoot2 == NULL ){
  fprintf(stderr, "ERROR: in check_is_include_helper(), input param error\n");
  return INPUT_PARAM_ERROR;
 }

 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

找不到

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm