一个二叉树是否包含另一个二叉树

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 "）;
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 ",
pPreOrder[0], pInOrder[0]）;
fprintf（stderr, "note: root_data_index is -1, total nodes: %d ", 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 ", 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 ",
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 ",
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（） "）;
while（ *ptr ！= "" ）{
if（（ *ptr >= "0" ） && （ *ptr <= "9"））{
++numLen;
} else if（ *ptr == " " ）{
*ptr = "";
if（ numLen > 0 && numLen <= MAX_NUM_LEN ）{
pOrder[i] = atoi（ ptr - numLen ）;
fprintf（stderr, "note: num is: %d ", 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 ", pOrder[i]）;
} if（ get_no_num ！= 0 ）
return get_no_num; *order_len = i + 1;
fprintf（stderr, "note: finish get_traver_data（） "）;
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 ",
__FILE__, __LINE__）;
return INPUT_PARAM_ERROR;
} if（ access（ file_name, F_OK ）！= 0）{
fprintf（stderr, "ERROR: file（%s） not exsit ", 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 ", file_name）;
return FILE_IS_EMTPY;
}
fprintf（stderr, "note: file size: %ld ", fstat.st_size）; char * buf = NULL;
buf = （char *）malloc（（file_size + 1） * sizeof（ char ））;
if（ buf == NULL ）{
fprintf（stderr, "ERROR: alloca buffer failure "）;
return ALLOCA_FAILURE;
} FILE *input = fopen（ file_name, "rb"）;
if（ input == NULL ）{
fprintf（stderr, "ERROR: can"t open input file [%s] ", 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] == " " ）
buf[ buf_len - 1 ] = "";
fprintf（stderr, "note: current line is: %s ", 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 "）;
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 "）;
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 ", 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（） "）;
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 ", 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 ", 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 "）;
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 ",
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 "）;
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 ", 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 ", __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） ", 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） ", 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） ", 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） ", 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 "）;
goto end;
}
#endif
printf（"NOTE: success to find b btree in a btree "）; 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本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-01/111626.htm