두 갈래 나무(16)---한 갈래 나무가 다른 두 갈래 나무를 포함하는지 여부

11965 단어 두 갈래 나무
두 갈래 나무 문제 집합
2. 문제 설명
두 갈래 트리 A와 B의 각 노드의 데이터(int형 데이터)는 서로 다른 파일에 저장되고 저장 방식은 앞의 두 갈래 트리와 중간의 두 갈래 트리를 재구성하고 두 갈래 트리 A가 두 갈래 트리 B를 포함하는지 판단한다.
3. 알고리즘 설명
(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 != '\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
", 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 ] = '\0'; 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
찾을 수 없습니다.

좋은 웹페이지 즐겨찾기