WoohyunKing의 개발 성장일지

순회하는 것 자체가 재귀이므로, 재귀 함수로 만들면 구현하는 과정을 이해하기 쉽다. 또한 순서만 조금씩 바꾸면 바로 중위 순회와 후위 순회로 변경할 수 있다. 전위 순회 함수 만들기 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): 특정 노드를 루트로 생각할 때 생기는 트리 크기(..