이진 트리

위키백과 ― 우리 모두의 백과사전.

전산학에서 이진 트리 (binary tree)란 한 노드가 최대 두 개의 자식 노드를 가지는 트리를 뜻한다. 그래프 이론에서 그래프의 특별한 형태를 이진트리로서 표시한다.

[편집] 개요

이진 트리는 빈 트리이거나 하나의 자식노드 또는 왼쪽과 오른쪽 자식노드를 가진 루트노드로 구성되며, 이 자식 노드는 내부 노드가 될 수 있다. 루트노드에서 시작한 각 노드는 최대한 두개의 자식 노드를 가질 수 있으며, 그 자식노드는 정확히 왼쪽과 오른쪽 노드로 분할할 수 있다.

[편집] 특징

h(>=0)를 높이, n을 노드 수, i(>=0)를 레벨이라고 할 때 이진 트리는 다음과 같은 특징이 있다.

1. n = (외부노드 = 잎노드) + (내부노드).
2. (외부노드) = (내부노드) + 1.
3. (노드 on level-i) <= 2^i
4. h + 1 <= (외부노드) <= 2^h
5. log(외부노드) <= h
6. h + 1 <= (외부노드) <= 2^h

[편집] 이진 트리 탐색

이진 트리의 모든 노드를 방문하는 것 혹은 방문하여 어떤 작업을 하는 것을 이진 트리 탐색이라고 한다. 이진 트리 탐색의 방법에는 여러 가지가 있으며, 다음의 방법들이 유명하다.

1. in-order  : 왼쪽 자식노드, 내 노드, 오른쪽 자식노드 순서로 방문한다.
2. pre-order  : 내 노드, 왼쪽 자식노드, 오른쪽 자식노드 순서로 방문한다.
3. post-order : 왼쪽 자식노드, 오른쪽 자식노드, 내 노드 순서로 방문한다.
4. level-order : 내 노드, 내 노드로부터 깊이 1인 노드들, 내 노드로부터 깊이 2인 노드들, ... , 내 노드로부터 깊이 N인 노드들 (N: 나(트리)의 깊이)

이 글은 전산학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.