이진트리

<이진트리(Binary Tree)>

트리의 노드 구조를 일정하게 정의하여 트리의 구현과 연산이 쉽도록 정의한 트리이다. 이진 트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드 만을 가진다.
- 부모 노드와 자식 노드 수와의 관계 -> 1:2
- 공백 노드도 자식 노드로 취급한다.
0 ≤ 노드의 차수 ≤ 2

[이진트리의 특성]
1. n개의 노드를 가진 이진 트리는 항상 (n-1)개의 간선을 가진다.
− 루트를 제외한 (n-1)개의 노드가 부모 노드와 연결되는 한 개의 간선을 가짐

2. 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2^(h+1)-1)개가 된다.
− 이진 트리의 높이가 h가 되려면 한 레벨에 최소한 한 개의 노드가 있어야 하므로 높이가 h인 이진 트리의 최소 노드의 개수는 (h+1)개
− 하나의 노드는 최대 2개의 자식 노드를 가질 수 있으므로 레벨 i에서의 노드의 최대 개수는 2i개 이므로 높이가 h인 이진 트리 전체의 노드 개수는 2^(h+1)-1 개

 

ex) 높이가 3이면서 최소의 노드를 갖는 이진트리와 최대의 노드를 갖는 이진트리

<포화이진트리(Full Binary Tree)>

​모든 레벨에 노드가 포화상태로 차 있는 이진 트리이다. 높이가 h일 때, 최대의 노드 개수인 (2^(h+1)-1) 의 노드를 가진 이진 트리이다.

<완전 이진 트리(Complete Binary Tree)>

높이가 h이고 노드 수가 n개일 때 (단, h+1 ≤ n < 2^(h+1)-1 ), 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리

<편향 이진 트리(Skewed Binary Tree)>

높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리 

왼쪽 편향 이진 트리
−모든 노드가 왼쪽 자식 노드만을 가진 편향 이진 트리
오른쪽 편향 이진 트리

−모든 노드가 오른쪽 자식 노드만을 가진 편향 이진 트리

<연결 자료구조를 이용한 이진트리>

단순 연결 리스트를 사용하여 구현. 이진 트리의 모든 노드는 최대 2개의 자식 노드를 가지므로 일정한 구조의 단순 연결 리스트 노드를 사용하여 구현

[구조체]

typedef struct treeNode {
char data;
struct treeNode *left;
struct treeNode *right;
} treeNode;

 

[연결 자료구조의 이진트리 그림]

<이진 트리의 순회(traversal)>

계층적 구조로 저장되어있는 트리의 모든 노드를 방문하여 데이터를 처리하는 연산이다.
순회를 위해 수행할 수 있는 작업 정의
⑴ 현재 노드를 방문하여 데이터를 읽는 작업 D
⑵ 현재 노드의 왼쪽 서브트리로 이동하는 작업 L
⑶ 현재 노드의 오른쪽 서브트리로 이동하는 작업 R

 

 

1. 전위 순회(preorder traversal) : root-left-right
[수행 방법]
① 현재 노드 n을 방문하여 처리한다. : D(루트에서 아래로 내려서 처리)
② 현재 노드 n의 왼쪽 서브트리로 이동한다. : L(왼쪽 하위 트리 끝까지 처리)
③ 현재 노드 n의 오른쪽 서브트리로 이동한다. : R(오른쪽 하위 트리 처리)

2. 중위 순회(inorder traversal) : left – root - right
[수행 방법]
① 현재 노드 n의 왼쪽 서브트리로 이동한다. : L(왼쪽 하위 트리를 시작하여)
② 현재 노드 n을 방문하여 처리한다. : D(하위에 걸친 루트까지 거친 후)
③ 현재 노드 n의 오른쪽 서브트리로 이동한다. : R(오른쪽 하위 트리로 이동)

3. 순회(postorder traversal): left - right - root
[수행 방법]
① 현재 노드 n의 왼쪽 서브트리로 이동한다. : L(왼쪽 하위트리부터 시작후)
② 현재 노드 n의 오른쪽 서브트리로 이동한다. : R(우측 형제노드이동방문후)
③ 현재 노드 n을 방문하여 처리한다. : D(루트 노드까지만이동후, 다시 L)

Copyrightⓒ2014 By 한빛아카데미(주)