배열로 포장 된 inorder (LDR) 이진 트리를 C++의 이진 트리로 다시 변환하는 방법

Question

나는 순서대로 있기 때문에 트리 값의 정렬 된 배열을 만드는 int* binToArrayInOrder(TreeRoot* tr)이라는 함수를 이미 가지고 있습니다.

주어진 배열에서 없이없이 사전 주문 배열의 다른 트리 정보와 같은 트리를 다시 구성 할 수 있습니까?

배열을 C의 텍스트 파일에 쓰려면 어떻게해야합니까? 코드를 보여주십시오.

Answer 1

[1] 배열 요소를 다시 이진 트리에 다시 삽입 할 수 있습니다. 밸런싱 알고리즘에 따라 트리를 배열로 추출했을 때 트리가 정확하게 보이지 않을 수도 있습니다.

[2]이 어때요?

void print_array (int *array, size_t sz, FILE *f) { 
    if (!sz) return; 
    fprintf(f, "%d\n", *array); 
    print_array(array+1, sz-1, f); 
} 

의견을 통해 실제 질문은 이진 트리를 디스크에 저장 한 다음 복원하는 방법입니다. 이것은 데이터 구조 직렬화 문제입니다. 이 문제에 대해, 주문형 걷기는 아마도 당신이 원하는 것이 아닙니다. 대신, 직렬화는 데이터 구조가 배치되는 방법을 반영해야합니다. 이제

struct binary_node_file_data { 
    char data_[MAX_BINARY_NODE_DATA_SIZE]; 
    int parent_; 
}; 

, 당신은 당신의 노드를 채우는 이진 트리의 예약 주문 탐색을 수행 할 수 있습니다 : 그래서, 당신은 바이너리 노드를 설명하는 기록이 필요합니다. 여기

struct binary_node_fila_data *bfd = malloc(sizeof(*bfd)*nodeCount); 
int count = 0; 
populate_binary_node_file(tree, bfd, &count, -1); 

void populate_binary_node_file(binary_tree_t *tree, 
           struct binary_node_file_data *bfd, 
           int *count, 
           int parent) { 
    if (tree) { 
     int me = *count; 
     *count += 1; 
     export_binary_node_data(tree, &bfd[me], parent); 
     populate_binary_node_file(tree->left_subtree, bfd, count, me); 
     populate_binary_node_file(tree->right_subtree, bfd, count, me); 
    } 
} 

, 나는 -1가 NULL 포인터처럼 취급 될 것으로 기대합니다. 그런 다음 bfd을 파일로 덤프하십시오. 나는 나무를 운동으로 되돌려 놓을 것입니다. 문제를 조금 더 생각해 보면, 순회가 선주문인지 또는 순서가 맞는지 (또는 후행인지) 문제가되지 않습니다. 복원 단계에서는 모든 자식이 부모를 찾아서 왼쪽 및 오른쪽 포인터를 올바르게 채울 수 있어야합니다.

Answer 2

첫 번째 질문은 아니오입니다. 노드의 inorder 목록은 동일한 트리를 재구성 할 수 없도록합니다. 예를 들어

, 나무

3 
2 
1 

1 2 3 따라서 중위 순회 1 2 3

에게 나무

2 
1 3 

도 생산을 생산, 당신은 말할 수없는 나무가 주어진 1 2 3을 생산하는 데 사용되었습니다.

두 번째 질문 : 저는 STL 파일을 사용하지 않았습니다. I/O 아직, 미안.