티스토리 뷰
참고: https://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/
트리 순회?
트리 순회는 각 노드를 딱 한 번씩 체계적으로 순회하는 것을 말한다. 그 종류는 루트 노트의 방문 순서에 따라 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder)가 있다.
트리 관련 알고리즘 문제를 풀면 가끔 두 개의 순회 결과만 주어지고 트리를 복구하거나, 나머지 순회 결과를 구하는 문제를 만날 때가 있다. 트리를 복구할 수 있으면 나머지 순회를 구할 수 있기 때문에 두 문제는 거의 동일한 것으로 볼 수 있을 것이다.
오늘은 두 가지 순회를 가지고 트리를 복구하는 알고리즘을 정리한다. 단, 전위 순회와 후위 순회만 주어진 경우는 일반적인 트리가 아닌 전이진 트리(Full Binary Tree)만 복구가 가능하다. 따라서 이는 추후에 따로 정리하도록 한다.
1. Preorder & Inorder
Inorder sequence: D B E A F C
Preorder sequence: A B D E C F
전위 순회 결과의 가장 왼쪽 원소는 전체 트리의 루트를 의미한다. 즉, 'A'가 전체 트리의 원소가 되는 것이다.
그리고 트리의 루트인 'A'를 기준으로 중위 순회 결과에서는 왼쪽이 왼쪽 서브트리의 원소, 오른쪽이 오른쪽 서브 트리의 원소가 될 것이다.
A
↙ ↘
D B E F C
그리고 전위 순회 결과에서 'A' 다음 원소인 'B'는 왼쪽 서브트리의 루트이다. 따라서 위 과정과 동일하게 재귀적으로 수행하면 아래와 같이 된다.
A
↙ ↘
B F C
↙ ↘
D E 복구된 최종 트리는 아래와 같다.
A
↙ ↘
B C
↙ ↘ ↙
D E F알고리즘을 정리하면,
1. 전위 순회 결과에서 루트를 선택한 후 인덱스를 1 증가 시킨다.
2. 중위 순회 결과에서 루트의 인덱스를 구하고, 왼쪽 서브 트리와 오른쪽 서브 트리로 나눈다.
3. 왼쪽 서브 트리를 재귀적으로 수행하고, 오른쪽 서브 트리를 재귀적으로 수행한다.
Python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
"""
in_s: start index of inorder
in_e: end index of inorder
p_idx: current index of preorder
"""
def build_tree(inorder, preorder, in_s, in_e):
global p_idx
if in_s > in_e:
return
node = Node(preorder[p_idx])
p_idx += 1
index = search(inorder, in_s, in_e, node.value)
node.left = build_tree(inorder, preorder, in_s, index-1)
node.right = build_tree(inorder, preorder, index+1, in_e)
return node
# find index of target in inorder from start to end
def search(inorder, start, end, target):
for i in range(start, end+1):
if inorder[i] == target:
return i
p_idx = 0
def main():
inorder = ['D', 'B', 'E', 'A', 'F', 'C']
preorder = ['A', 'B', 'D', 'E', 'C', 'F']
root = build_tree(inorder, preorder, 0, len(inorder)-1)
postorder_travlesal(root)
def postorder_travlesal(node):
if node:
postorder_travlesal(node.left)
postorder_travlesal(node.right)
print(node.value, end=" ")
main()2. Inorder & Postorder
Inorder sequence: D B E A F C
Postorder sequence: D E B F C A
후위 순회 결과를 통해서 먼저 알 수 있는 것은 가장 오른쪽 원소인 'A'가 전체 트리의 루트라는 것이다. 따라서 'A'를 기준으로 중위 순회 결과를 왼쪽과 오른쪽으로 나눌 수 있다.
A
↙ ↘
D B E F C그리고 'A'의 이전 원소인 'C'는 오른쪽 서브 트리의 루트다. 'C'를 기준으로 오른쪽 서브 트리를 재귀적으로 나누면 아래와 같다. 그리고 또 나누어진 서브 트리에서 'F'는 루트이자 리프이기 때문에 재귀를 종료하고 왼쪽 서브 트리로 넘어간다.
A
↙ ↘
D B E C
↙
F 다음 'B'를 기준으로 나누면 아래와 같다.
A
↙ ↘
B C
↙ ↘ ↙
D E F 최종적으로 1번의 트리와 같아진다.
Python
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
"""
in_s: start index of inorder
in_e: end index of inorder
p_idx: current index of postorder
"""
def build_tree(inorder, postorder, in_s, in_e):
global p_idx
if in_s > in_e:
return
node = Node(postorder[p_idx])
p_idx -= 1
index = search(inorder, in_s, in_e, node.value)
node.right = build_tree(inorder, postorder, index+1, in_e)
node.left = build_tree(inorder, postorder, in_s, index-1)
return node
# find index of target in inorder from start to end
def search(inorder, start, end, target):
for i in range(start, end+1):
if inorder[i] == target:
return i
p_idx = 0
def main():
global p_idx
inorder = ['D', 'B', 'E', 'A', 'F', 'C']
postorder = ['D', 'E', 'B', 'F', 'C', 'A']
p_idx = len(postorder) - 1
root = build_tree(inorder, postorder, 0, len(inorder)-1)
preorder_travlesal(root)
def preorder_travlesal(node):
if node:
print(node.value, end=" ")
preorder_travlesal(node.left)
preorder_travlesal(node.right)
main()