하나의 이진 트리가 있고 직렬화 및 역직렬화해야 한다고 가정합니다. 직렬화는 데이터 구조나 개체를 비트 시퀀스로 변환하여 파일이나 메모리 버퍼에 저장할 수 있고 나중에 동일하거나 다른 컴퓨터 환경에서 재구성할 수 있다는 것을 알고 있습니다.
여기서 우리는 이진 트리를 직렬화 및 역직렬화하는 알고리즘을 고안해야 합니다. 바이너리 트리는 각 노드에 2개 이하의 자식이 있는 루트 트리입니다.
따라서 입력이 다음과 같으면
그러면 출력은 Serialize − 1 2 3 4 5 N N N N N Deserialized Tree:4 2 5 1 3이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
serialize() 함수를 정의하면 루트가 됩니다.
-
ret :=빈 문자열
-
하나의 대기열 정의 q
-
루트를 q에 삽입
-
동안(q가 비어 있지 않음) -
를 수행합니다.-
curr =q
의 첫 번째 요소 -
q에서 요소 삭제
-
curr을 사용할 수 없는 경우 -
-
ret :=ret "N" 연결
-
ret :=ret 공백 연결
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
ret :=ret + 현재의 값
-
ret :=ret + 공백
-
q 끝에서 curr의 왼쪽
-
q 끝에 있는 curr의 오른쪽
-
-
리턴 렛
-
deserialize() 함수를 정의하면 데이터가 필요합니다.
-
data[0]이 'N'과 같으면 -
-
NULL 반환
-
-
temp :=빈 문자열
-
배열 정의 v
-
for initialize i :=0, i − 데이터 크기, 업데이트(i 1 증가), −
-
data[i]가 공백과 같으면 -
-
v
끝에 temp 삽입 -
temp :=빈 문자열
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
임시 :=임시 + 데이터[i]
-
-
newRoot =v[0]
이 있는 새 노드 -
하나의 대기열 정의 q
-
q에 newRoot 삽입
-
나는 :=1
-
동안 (q가 비어 있지 않고 i
-
부모 =q
의 첫 번째 요소 -
q에서 요소 삭제
-
v[i]가 "N"과 같지 않으면 -
-
부모의 왼쪽 :=v[i]
가 있는 새 노드 -
부모의 왼쪽을 q
에 삽입
-
-
(i를 1씩 증가)
-
v[i]가 "N"과 같지 않으면 -
-
부모의 오른쪽 :=v[i]
가 있는 새 노드 -
부모의 오른쪽을 q
에 삽입
-
-
(i를 1씩 증가)
-
-
newRoot 반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val) {
queue<TreeNode *> q;
q.push(*root);
while (q.size()) {
TreeNode *temp = q.front();
q.pop();
if (!temp->left) {
if (val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}
else {
q.push(temp->left);
}
if (!temp->right) {
if (val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}
else {
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v) {
TreeNode *root = new TreeNode(v[0]);
for (int i = 1; i < v.size(); i++) {
insert(&root, v[i]);
}
return root;
}
void inord(TreeNode *root) {
if (root != NULL) {
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Codec {
public:
string serialize(TreeNode *root) {
string ret = "";
queue<TreeNode *> q;
q.push(root);
while (!q.empty()) {
TreeNode *curr = q.front();
q.pop();
if (!curr) {
ret += "N";
ret += " ";
continue;
}
ret += to_string(curr->val);
ret += " ";
q.push(curr->left);
q.push(curr->right);
}
return ret;
}
TreeNode *deserialize(string data) {
if (data[0] == 'N')
return NULL;
string temp = "";
vector<string> v;
for (int i = 0; i < data.size(); i++) {
if (data[i] == ' ') {
v.push_back(temp);
temp = "";
continue;
}
temp += data[i];
}
TreeNode *newRoot = new TreeNode(stoi(v[0]));
queue<TreeNode *> q;
q.push(newRoot);
int i = 1;
while (!q.empty() && i < v.size()) {
TreeNode *parent = q.front();
q.pop();
if (v[i] != "N") {
parent->left = new TreeNode(stoi(v[i]));
q.push(parent->left);
}
i++;
if (v[i] != "N") {
parent->right = new TreeNode(stoi(v[i]));
q.push(parent->right);
}
i++;
}
return newRoot;
}
};
main() {
Codec ob;
vector<int> v = {1,2,3,4,5};
TreeNode *root = make_tree(v);
cout << "Given Tree: ";
inord(root);
cout << endl;
string ser = ob.serialize(root);
cout << "Serialize: " << ser << endl;
TreeNode *deser = ob.deserialize(ser);
cout << "Deserialized Tree: ";
inord(root);
} 입력
1,2,3,4,5
출력
Given Tree: 4 2 5 1 3 Serialize: 1 2 3 4 5 N N N N N N Deserialized Tree: 4 2 5 1 3