이 저작물은 개발남노씨 - 코딩테스트 [ ALL IN ONE ] (opens in a new tab)을 참고하여 작성되었습니다.
이진 트리
class Node :
def __init__(self, value = 0, left = None, right = None) :
self.value = value
self.left = left
self.right = right
class BinaryTree :
def __init__(self) :
self.root = None
bt = BinaryTree()
bt.root = Node(value=1)
bt.root.left = Node(value=2)
bt.root.right = Node(value=3)
bt.root.left.left = Node(value=4)
bt.root.left.right = Node(value=5)
bt.root.right.left = Node(value=6)
bt.root.right.right = Node(value=7)일반적인 트리
class Node:
def __init__(self, data):
self.data = data
self.children = []
def add_child(self, node):
self.children.append(node)
class Tree:
def __init__(self, root):
self.root = Node(root)
def print_tree(self):
self._print_tree(self.root)
def _print_tree(self, node, level=0):
print(' ' * level + str(node.data))
for child in node.children:
self._print_tree(child, level+1)
tree = Tree('root')
tree.root.add_child(Node('child_1'))
tree.root.add_child(Node('child_2'))
tree.root.children[0].add_child(Node('child_1_1'))
tree.root.children[0].add_child(Node('child_1_2'))
tree.print_tree()BFS (Breadth-First Search)
너비 우선 탐색이라고 불리며, 상세 동작을 봤을 때 상단 > 자식 노드 > 자식노드의 자식노드 이런식으로 탐색하는 방식이다.
def bfs(root: Node) -> list :
visited = []
if root is None :
return []
q = deque()
q.append(root)
while q :
cur_node = q.popleft()
visited.append(cur_node.value)
if cur_node.left :
q.append(cur_node.left)
if cur_node.right :
q.append(cur_node.right)
return visited
print(bfs(bt.root))DFS (Depth-First Search)
깊이 우선 탐색, 특정 방향의 가장 깊은 곳 > 얕은 곳으로 짚고 넘오는 형식의 탐색 방법
def dfs(root: Node) :
if root is None :
return
dfs(root.left)
dfs(root.right)전위순회(preorder)
자식 노드에 방문하기 전에 자기 자신부터 방문을 한다.
visited = []
def dfs(node: Node) :
if node is None :
return
visited.append(node)
dfs(node.left)
dfs(node.right)중위순회(inorder)
왼쪽에 있는 모든 노드를 확인하고 나서 자기 자신을 확인하는 방식이다.
visited = []
def dfs(node: Node) :
if node is None :
return
dfs(node.left)
visited.append(node)
dfs(node.right)후위순회(postorder)
자식을 다 방문한 다음에 자기 자신을 방문하는 방식이다.
visited = []
def dfs(node: Node) :
if node is None :
return
dfs(node.left)
dfs(node.right)
visited.append(node)