배열로 트리 구현
이진트리를 배열로 표현할 수 있습니다. 부모노드와 자식노드는 다음의 인덱스 관계를 갖습니다.
[배열활용] 부모노드와 자식노드의 인덱스 관계
부모노드의 인덱스: n
자식노드의 인덱스: 2*n + 1, 2*n + 2[배열활용] 부모-자식 노드의 관계 표현
my_tree = ['A','B','C','D','E','F',None,'G']
i = 0
n = len(my_tree)
while i < n:
if my_tree[i]:
print(f"Parent: {my_tree[i]}", end=', ')
left = 2 * i + 1
right = 2 * i + 2
if left < n and my_tree[left] is not None:
print(f"Left: {my_tree[left]}", end=', ')
if right < n and my_tree[right] is not None:
print(f"Right: {my_tree[right]}", end=', ')
print()
i += 1
[배열활용] 자식노드의 부모노드 찾기
def find_parent(child: Any ,tree: list) -> None:
child_idx = tree.index(child)
parent_idx = 0
if child_idx % 2 == 1:
parent_idx = (child_idx - 1) // 2
else:
parent_idx = (child_idx - 2) // 2
print(f"Parent of {child}: {tree[parent_idx]}")
[배열활용] 전위순회
def pre_order(tree: Any, i = 0) -> None:
"""트리의 전위순회"""
if i < len(tree):
print(tree[i], end = ' ')
left = 2 * i + 1
right = 2 * i + 2
if left < len(tree) and tree[left] is not None:
pre_order(tree, left)
if right < len(tree) and tree[right] is not None:
pre_order(tree, right)[배열활용] 중위순회
def in_order(tree: Any, i = 0) -> None:
"""트리의 중위순회"""
if i < len(tree):
left = 2 * i + 1
right = 2 * i + 2
if left < len(tree) and tree[left] is not None:
in_order(tree, left)
print(tree[i], end = ' ')
if right < len(tree) and tree[right] is not None:
in_order(tree, right)[배열활용] 후위순회
def post_order(tree: Any, i = 0) -> None:
"""트리의 후위순회"""
if i < len(tree):
left = 2 * i + 1
right = 2 * i + 2
if left < len(tree) and tree[left] is not None:
post_order(tree, left)
if right < len(tree) and tree[right] is not None:
post_order(tree, right)
print(tree[i], end = ' ')연결리스트로 구현
from typing import Any
from collections import deque
class Node:
"""노드: 키, left, right 값을 가짐"""
def __init__(self, key: Any):
self.key = key
self.left = None
self.right = None
class Tree:
"""트리 구현: root"""
def __init__(self):
self.root = None
def level_traversal(self):
if not self.root:
return []
reservation = deque()
visited = []
reservation.append(self.root)
while reservation:
current_node = reservation.popleft()
visited.append(current_node)
if current_node.left is not None:
reservation.append(current_node.left)
if current_node.right is not None:
reservation.append(current_node.right)
return visited
def in_order_traversal(self):
def in_order(node):
if node is None:
return
in_order(node.left)
res.append(node.key)
in_order(node.right)
res = []
in_order(self.root)
return res
def post_order_traversal(self):
def post_order(node):
if node is None:
return
post_order(node.left)
post_order(node.right)
res.append(node.key)
res = []
post_order(self.root)
return res
if __name__ == "__main__":
tree = Tree()
tree.root = Node("A")
tree.root.left = Node("B")
tree.root.right = Node("C")
tree.root.left.left = Node("D")
tree.root.left.right = Node("E")
tree.root.right.left = Node("F")
tree.root.right.right = Node("G")
print(tree)
print(*[x.key for x in tree.level_traversal()])
print(tree.in_order_traversal())
print(tree.post_order_traversal())