이진 검색 트리를 직렬화 및 역직렬화하는 알고리즘을 설계한다고 가정합니다. 직렬화는 파일이나 메모리 버퍼에 저장하거나 네트워크 연결 링크를 통해 전송할 수 있도록 무언가(데이터 구조 또는 개체)를 비트 시퀀스로 변환하는 프로세스입니다. 나중에 재구성할 수 있으며 이 프로세스는 직렬화 해제입니다.
따라서 입력이 [5,2,9,1,3,7]과 같으면 출력은 직렬화된 출력 5.2.9.1.3.7.N.N.N.N.N.N.N 직렬화된 출력이 됩니다. 1, 2, 3, 5, 7, 9, (중위 순회)
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
serialize() 함수를 정의합니다. 이것은 뿌리를 내릴 것입니다
-
res :=새 목록
-
하나의 대기열을 정의하고 루트 삽입
-
대기열이 비어 있지 않은 동안 수행
-
대기열이 비어 있지 않은 동안 수행
-
현재 :=대기열[0]
-
res의 끝에 전류 삽입
-
대기열에서 첫 번째 요소 삭제
-
전류가 0이 아니면
-
루프에서 나오다
-
-
-
현재가 null이면
-
루프에서 나오다
-
-
current.left가 null이 아니면
-
큐 끝에 current.left 삽입
-
-
그렇지 않으면
-
대기열 끝에 없음 삽입
-
-
current.right가 null이 아니면
-
큐 끝에 current.right 삽입
-
-
그렇지 않으면
-
대기열 끝에 없음 삽입
-
-
-
s:=빈 문자열
-
범위 0에서 res 크기까지의 i에 대해
-
res[i]가 0이 아니면
-
s :=s 연결 res[i].data
-
-
그렇지 않으면
-
s :=s "N" 연결
-
-
i가 res -1의 크기와 같으면
-
루프에서 나오다
-
-
s :=s 연결 "."
-
-
반환 s
-
deserialize() 함수를 정의합니다. 데이터가 필요합니다
-
data :=데이터를 점으로 나눈 부분의 목록
-
스택 :=새 목록
-
data[0]이 'N'과 같으면
-
반환 없음
-
-
root :=데이터 데이터로 새 노드 생성[0]
-
스택 끝에 루트 삽입
-
나는 :=1
-
현재 :=0
-
동안 <데이터 크기, 수행
-
왼쪽:=거짓
-
data[i]가 'N'과 같지 않으면
-
temp :=데이터 데이터로 새 노드 생성[i]
-
스택[현재].left :=임시
-
스택 끝에 temp 삽입
-
-
그렇지 않으면
-
스택[현재].left :=없음
-
-
나는 :=나는 + 1
-
data[i]가 'N'과 같지 않으면
-
temp :=데이터 데이터로 새 노드 생성[i]
-
스택[현재].right :=임시
-
스택 끝에 temp 삽입
-
-
그렇지 않으면
-
스택[현재].right :=없음
-
-
현재 :=현재 + 1
-
나는 :=나는 + 1
-
-
루트 반환
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
def insert(temp,data):
que = []
que.append(temp)
while (len(que)):
temp = que[0]
que.pop(0)
if (not temp.left):
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if (not temp.right):
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def print_tree(root):
#print using inorder traversal
if root is not None:
print_tree(root.left)
print(root.data, end = ', ')
print_tree(root.right)
class Codec:
def serialize(self, root):
res =[]
queue = [root]
while queue:
while True and queue:
current = queue[0]
res.append(current)
queue.pop(0)
if current:
break
if not current:
break
if current.left:
queue.append(current.left)
else:
queue.append(None)
if current.right:
queue.append(current.right)
else:
queue.append(None)
s=""
for i in range(len(res)):
if res[i]:
s+=str(res[i].data)
else:
s+="N"
if i == len(res)-1:
break
s+="."
return s
def deserialize(self, data):
data = data.split(".")
stack = []
if data[0]=='N':
return None
root = TreeNode(int(data[0]))
stack.append(root)
i = 1
current = 0
while i <len(data):
left= False
if data[i] !='N':
temp = TreeNode(int(data[i]))
stack[current].left = temp
stack.append(temp)
else:
stack[current].left = None
i+=1
if data[i] !='N':
temp = TreeNode(int(data[i]))
stack[current].right = temp
stack.append(temp)
else:
stack[current].right = None
current+=1
i+=1
return root
ob = Codec()
root = make_tree([5,2,9,1,3,7])
ser = ob.serialize(root)
print('Serialization:',ser)
print_tree(ob.deserialize(ser)) 입력
[5,2,9,1,3,7]
출력
Serialization: 5.2.9.1.3.7.N.N.N.N.N.N.N 1, 2, 3, 5, 7, 9,