하나의 N-ary 트리가 있고 직렬화 및 역직렬화해야 한다고 가정합니다. 직렬화는 데이터 구조나 개체를 비트 시퀀스로 변환하여 파일이나 메모리 버퍼에 저장할 수 있고 나중에 동일하거나 다른 컴퓨터 환경에서 재구성할 수 있다는 것을 알고 있습니다.
여기서 우리는 N-ary 트리를 직렬화 및 역직렬화하는 알고리즘을 고안해야 합니다. N-ary 트리는 각 노드에 N 이하의 자식이 있는 루트 트리입니다.
따라서 입력이 다음과 같으면
그러면 출력은 Serialize:1 #3 2 4 #5 6 ##### 및 Deserialized Tree:1[3[5, 6, ], 2, 4, ]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
createVector() 함수를 정의하면 s가 필요합니다.
-
하나의 2D 배열 ret 정의
-
배열 tempv 정의
-
temp :=빈 문자열
-
initialize i :=0의 경우, i
-
s[i]가 공백과 같지 않고 s[i]가 '#'과 같지 않으면 -
-
온도 :=온도 + s[i]
-
-
그렇지 않으면 s[i]가 공백 문자열과 같을 때 -
-
tempv의 끝에 temp 정수 삽입
-
temp :=빈 문자열
-
-
그렇지 않으면 s[i]가 '#'과 같을 때 -
-
ret 끝에 tempv 삽입
-
temp :=빈 문자열
-
클리어 tempv
-
-
-
동안 (ret가 비어 있지 않고 ret의 마지막 요소가 0과 동일), do -
-
ret에서 마지막 요소 삭제
-
-
리턴 렛
-
serialize() 함수를 정의하면 루트가 됩니다.
-
ret :=빈 문자열
-
루트가 아닌 경우 0이 아닌 경우 -
-
리턴 렛
-
-
하나의 대기열 정의 q
-
루트를 q에 삽입
-
rret :=ret 루트의 val 연결
-
ret :=ret 공백 연결
-
ret :=ret "#" 연결
-
동안(q가 비어 있지 않음) -
를 수행합니다.-
curr =q
의 첫 번째 요소 -
q에서 요소 삭제
-
for initialize i :=0, i
-
curr의 자식[i]인 경우 -
-
ret :=ret curr의 자식[i] 연결
-
curr의 자식[i]을 q
에 삽입
-
-
ret :=ret + 빈 문자열
-
-
ret :=ret "#" 연결
-
-
리턴 렛
-
deserialize() 함수를 정의하면 데이터가 필요합니다.
-
데이터 크기가 0과 같으면 -
-
null 반환
-
-
하나의 2D 배열 정의 v :=createVector(data)
-
ret :=값이 v[0, 0]인 새 노드
-
하나의 대기열 정의 q
-
q에 ret 삽입
-
나는 :=1
-
동안(q가 비어 있지 않고 i - v의 크기가 아님), 다음을 수행합니다. -
-
curr =q
의 첫 번째 요소 -
q에서 요소 삭제
-
초기화 j :=0일 때 j − v[i]의 크기, 업데이트(j를 1만큼 증가), −
-
노드 :=v[i, j]
-
temp =값 노드가 있는 새 노드
-
curr의 자식 끝에 temp 삽입
-
q에 temp 삽입
-
-
(i를 1씩 증가)
-
-
리턴 렛
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
string n_ary_to_str(Node *root){
string ret = "";
if(root){
ret = ret + to_string(root->val);
if(root->children.size() > 0){
ret += "[";
for(Node* child : root->children){
ret += n_ary_to_str(child) + ", ";
}
ret += "]";
}
}
return ret;
}
class Codec {
public:
vector<vector<int>>createVector(string s) {
vector<vector<int>> ret;
vector<int> tempv;
string temp = "";
for (int i = 0; i < s.size(); i++) {
if (s[i] != ' ' && s[i] != '#') {
temp += s[i];
}
else if (s[i] == ' ') {
tempv.push_back(stoi(temp));
temp = "";
}
else if (s[i] == '#') {
ret.push_back(tempv);
temp = "";
tempv.clear();
}
}
while (!ret.empty() && ret.back().size() == 0)
ret.pop_back();
return ret;
}
string serialize(Node *root) {
string ret = "";
if (!root)
return ret;
queue<Node *> q;
q.push(root);
ret += to_string(root->val);
ret += " ";
ret += "#";
while (!q.empty()) {
Node *curr = q.front();
q.pop();
for (int i = 0; i < curr->children.size(); i++) {
if (curr->children[i]) {
ret += to_string(curr->children[i]->val);
q.push(curr->children[i]);
}
ret += " ";
}
ret += "#";
}
return ret;
}
Node *deserialize(string data) {
Node *ret;
if (data.size() == 0)
return NULL;
vector<vector<int>> v = createVector(data);
ret = new Node(v[0][0]);
queue<Node *> q;
q.push(ret);
int i = 1;
while (!q.empty() && i < v.size()) {
Node *curr = q.front();
q.pop();
for (int j = 0; j < v[i].size(); j++) {
int node = v[i][j];
Node *temp = new Node(node);
curr->children.push_back(temp);
q.push(temp);
}
i++;
}
return ret;
}
};
main() {
Codec ob;
Node n5(5), n6(6);
Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6);
Node n2(2), n4(4);
Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2);
n1.children.push_back(&n4);
cout << "Given Tree: " << n_ary_to_str(&n1) << endl;
string ser = ob.serialize(&n1);
cout << "Serialize: " << ser << endl;
Node *deser = ob.deserialize(ser);
cout << "Deserialized Tree: " << n_ary_to_str(deser);
} 입력
Node n5(5), n6(6); Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6); Node n2(2), n4(4); Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2); n1.children.push_back(&n4);
출력
Given Tree: 1[3[5, 6, ], 2, 4, ] Serialize: 1 #3 2 4 #5 6 ##### Deserialized Tree: 1[3[5, 6, ], 2, 4, ]