[Tree] Queue를 이용한 레벨 순서 순회
레벨 순서 순회는 직관적이어서 쉽다. 과정을 나열하면 아래와 같다. 루트부터 방문하고, 루트의 왼쪽과 오른쪽을 방문한다. 루트 왼쪽 노드의 왼쪽과 오른쪽을 방문한다. 루트 오른쪽 노드의 왼쪽과 오른쪽을 방문한다. 즉, 현재 노드를 방문할 때 현재 노드의 왼쪽과 오른쪽 노드를 차례로 큐에 넣어 둔다. 그리고, 큐에서 순서대로 꺼내서 같은 방식으로 처리한다. 여기서는 파이썬의 리스트를 Queue로 사용한다. from collections import deque tree = ["A", "B", "C", "D", "E", "F", None, "G"] def levelorder(tree): if not tree: return queue = deque([0]) while queue: parent = queue.po..
2023. 9. 7.
[Tree] 이진트리 재귀 순회 함수 만들기
순회하는 것 자체가 재귀이므로, 재귀 함수로 만들면 구현하는 과정을 이해하기 쉽다. 또한 순서만 조금씩 바꾸면 바로 중위 순회와 후위 순회로 변경할 수 있다. 전위 순회 함수 만들기 tree = ["A", "B", "C", "D", "E", "F", None, "G"] n = len(tree) def preorder(tree, i): if i < len(tree): print(tree[i], end=" ") # 방문 처리(출력) left, right = 2*i + 1, 2*i + 2 if left < len(tree) and tree[left] is not None: preorder(tree,left) if right < len(tree) and tree[right] is not None: preorde..
2023. 9. 7.
