자료구조 : Binary Tree

rlask.rbs·2025년 9월 7일

binary tree 완전 이진 트리 이진 트리 자료구조 포화 이진 트리

[자료구조]

목록 보기

2/5

Binary Tree

트리 중에서도 각 노드가 최대 2개의 자식노드를 가질 때 이진트리(Binary Tree)라고 한다.
최대 2개이기 때문에 자식이 없을 수도 있고, 한개만 있을 수도 있다.
이때 자식 노드는 각각 왼쪽 자식노드(left-side node)와 오른쪽 자식노드(right-side node)로 표현한다.

같은 루트에 같은 자식노드 하나를 가지고 있어도
자식노드의 위치가 각각 왼쪽과 오른쪽으로 다르다면 그 두 트리는 서로 다른 트리이다.

Binary Tree의 종류

정 이진트리(Full Binary Tree)

이진트리(Binary Tree) 중에서도 모든 노드가 2개의 자식을 가지거나 자식이 없는 경우에는
정 이진트리(Full Binary Tree), 혹은 엄격한 이진트리(Strcit Binary Tree)라고 한다.
다시 말해서, 자식이 한 개인 경우가 없어야 정 이진트리다.

포화 이진트리(Perfect Binary Tree)

이진트리 중에서도 모든 노드가 2개의 자식을 가지고 leaf노드가 모두 같은 레벨(level)일때는
포화 이진트리(perfect binary tree)라고한다. 포화이진트리는 높이가 h인 포화 이진트리에서 노드 갯수는 2의 k+1 제곱 -1의 특징을 가진다.

완전이진트리(Complete binary tree)

완전이진트리(Complete binary tree)는 마지막을 제외하고 모든 노드가 채워져있어야 한다.
또 마지막 레벨의 노드는 다 채워져 있을 수도 있고 아닐 수도 있다.
노드는 왼쪽에서 오른쪽 방향으로 채워져야 한다.
그래서 어느 노드에 오른쪽 자식이 존재한다면, 왼쪽 자식노드도 가지고 있어야 완전한 이진트리이다.

포화이진트리(Perfect binary tree)도 완전이진트리(Complete binary tree)의 조건을 모두 충족하기 때문에 완전이진트리에 속할 수 있다.

그리고 위 왼쪽 그림의 트리처럼 오른쪽 자식노드는 있지만 왼쪽 자식 노드는 없다면 완전이진트리가 성립하지 않는다.
그리고 오른쪽 그림의 트리도 왼쪽부터 채우고 있지 않기 때문에 완전 이진트리가 될 수 없다.

이진트리의 특징

1차원 배열로 표현 할 수 있다.

완전이진트리는 루트에서 시작해서 왼쪽노드부터 오른쪽 노드까지 순서를 매기면, null값이 없다.

중간에 빈 값이 있는 이진트리는 배열로 표현하면 비어있는 공간의 인덱스에 null값이 들어간 1차원 배열로 표현할 수 있다.

이진트리의 연산

그래서 i번재 인덱스에 들어있는 노드의 부모는 i/2연산을 한 인덱스의 위치에 들어가 있게 되고,
노드 i의 왼쪽 자식은 i2를한 인덱스에 들어있게 된다.
노드 i의 오른쪽 자식은 i2+1을한 위치의 인덱스에서 찾을 수 있다.
배열로 표현된 트리에서 6번째 노드의 부모는 나누기2를 한 3번째 인덱스에 위치하게 되고,
노드 2의 왼쪽 자식 노드는 2*2를한 4번째 위치에서 찾을 수 있다는 것을 알 수 있다.

순회(circuit)

전위 순회(Preorder Traversal)

부모 -> 좌 -> 우
부모가 먼저니까 1 -> 좌를 살펴서 2 -> 또 좌가 있어서 3-> 또 좌가 있어서 5 -> 3은 봤으니까 이제 우로 가서 5 -> 3번 가족 다 봤으니 2의 우로 가서 6-> 6이 부모니까 좌인 7 -> 우 8 -> 2번 가족 다 봤으니 1의 우로 가서 9 -> 9의 좌인 10 -> 좌가 있으니까 11 -> 마지막 12

중위 순회(Inorder Traversal)

좌->부모->우
노드에 있는 번호대로 전위 순회가 탐색을 한다.
중위 순회는 tree를 크기 순으로 정렬할 때 쓰인다.
가장 간단하게 생각하는 것은, 왼쪽 벽면에서 가까운 노드부터 차례대로.
내가 3의 위치를 잘못 그려서 그런데 2보다 오른쪽에 있어야 한다..

후위 순회(Postorder Traversal)

좌 -> 우 -> 부모
후위 순회는 루트를 가장 마지막에 순회한다. 제일 왼쪽 끝네 있는 노드부터 순회하며 루트를 거치치 않고 오른쪽으로 이동해 순회한 후에, 마지막으로 루트를 방문한다. 후위 순회는 자식노드가 삭제되어야 상위 노드를 삭제 할 수 있으므로 트리를 삭제할 때 사용한다.