WoohyunKing의 개발 성장일지

레벨 순서 순회는 직관적이어서 쉽다. 과정을 나열하면 아래와 같다. 루트부터 방문하고, 루트의 왼쪽과 오른쪽을 방문한다. 루트 왼쪽 노드의 왼쪽과 오른쪽을 방문한다. 루트 오른쪽 노드의 왼쪽과 오른쪽을 방문한다. 즉, 현재 노드를 방문할 때 현재 노드의 왼쪽과 오른쪽 노드를 차례로 큐에 넣어 둔다. 그리고, 큐에서 순서대로 꺼내서 같은 방식으로 처리한다. 여기서는 파이썬의 리스트를 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..

순회하는 것 자체가 재귀이므로, 재귀 함수로 만들면 구현하는 과정을 이해하기 쉽다. 또한 순서만 조금씩 바꾸면 바로 중위 순회와 후위 순회로 변경할 수 있다. 전위 순회 함수 만들기 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..

배열로 이진트리 구현하기 파이썬으로 이진트리를 표현 방법에 (1) 배열을 이용하는 것과 (2) 연결 리스트를 이용하는 것이 있다. 먼저 배열로 이진트리를 나타내보자. 위 트리의 값을 레벨 순서대로 배열에 넣어 보면 다음과 같다. 위에서 보는 것처럼 부모 노드의 인덱스가 n일 때, 왼쪽 자식 노드의 인덱스는 (2 × n + 1)이며, 오른쪽 자식 노드의 인덱스는 (2 × n + 2)이다. 자식 노드가 2개 이하이므로 일정한 규칙에 따라 배열에 넣을 수 있다. 반대로 자식 노드의 부모 노드를 찾으려면, 자식 노드의 인덱스에서 1을 뺀 후에 2로 나눈 몫만 취하면 된다. 예를 들어 D의 부모 노드의 인덱스를 찾으면 (3 - 1) // 2 = 1이다. 인덱스 0은 비워두고, 인덱스 1부터 자료를 넣어 트리를 구..

트리란 ? 트리(tree)는 그래프(graph)의 한 형태로서, 순환(cycle)이 없는 연결 그래프라 한다. 트리의 구성 요소 노드(Node): 트리를 구성하는 기본 요소, 값(key or data)과 하위 노드를 가리키는 포인터(pointer)를 가진다. 간선(Edge): 노드와 노드를 연결한 선 (link) 위 그림처럼 트리는 루트에서 시작한다. 루트(Root): 부모 노드가 없는 최상위 노드. 모든 트리의 루트는 하나다. 부모(parent) 노드: 자식(child) 노드를 가진 노드 자식(child) 노드: 부모 노드의 하위 노드 형제(siblings) 노드: 부모가 같은 노드 리프(leaf) 노드: 자식이 없는 노드 서브 트리(sub tree): 특정 노드를 루트로 생각할 때 생기는 트리 크기(..