WoohyunKing의 개발 성장일지

배열로 이진트리 구현하기 파이썬으로 이진트리를 표현 방법에 (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): 특정 노드를 루트로 생각할 때 생기는 트리 크기(..