이진 트리

모든 노드의 차수가 2 이하인 트리

수학적으로, 이진트리의 구성에 관한 이론을 정리하기 쉽고, 컴퓨터 내부에서 구현하기도 효율적임

 

모든 노드가 2개 이하의 자식 노드를 가지므로, 일반성을 잃지 않고 '오른쪽', '왼쪽'이라는 방향 개념을 부여 가능

오른쪽 노드, 왼쪽 노드의 개념적 접근도 있음

 

포화 이진 트리

이진 트리의 각 레벨에서 허용되는 최대 개수 노드를 가지는 트리

 

완전 이진 트리

높이가 k인 이진 트리가 '0레벨'부터 'k-2 레벨'까지 다 채우고, 마지막 'k-1 레벨'에서 왼쪽부터 오른쪽으로 노드들이 차례로 채워진 이진트리

 

 

이진트리 구현

1. 배열을 이용한 구현

- 트리가 완전 이진 트리 또는 포화 이진 트리인 경우 낭비되는 공간이 없어 효율적

 

트리가 깊어질수록 기억장소 낭비가 2의 거듭제곱에 비례하며 낭비가 심해짐

 

2. 포인터를 이용한 이진트리 구현

struct node{
	struct node *left;
    struct node *right;
    int info;
}

 

 

이진 트리 연산

1. 이진트리 순회

이진 트리의 각 노드를 (빠짐없이 그리고 중복없이) 한 번씩 방문하는 것

 

2. 이진트리 전위 순회

루트노드 - 왼쪽 자식노드 - 오른쪽 자식노드 (P -> SL -> SR)

 

3. 이진트리 후위 순회

왼쪽  자식노드 - 오른쪽 자식노드 - 루트노드 (SL -> SR -> P)

 

4. 이진트리 중위 순회

왼쪽 자식노드 - 루트노드 - 오른쪽 자식노드 ( SL -> P -> SR)

 

5. 이진트리 생성/삽입/삭제

- 일반적인 이진트리를 생성하는 것은 연결 리스트 연산을 사용

- 첫 노드를 생성하면 루트 노드가 되고, 새로운 노드를 추가하려면 연결 리스트의 삽입 연산 사용

- 노드를 삭제할 때 삭제하려는 노드가 리프노드인 경우는 해당 노드를 가리키는 포인터를 NULL로 지정하면 됨

- 리프노드가 아닌 경우에는 삭제하려는 노드의 자식 노드에 대한 처리를 추가로 해주어야 함

 

일반 트리를 이진 트리로 변환하는 방법

일반 트리에 대하여 각 노드의 형제들을 연결 -> 각 노드에 대하여 왼쪽 링크만 남기고 모두 제거

루트 노드는 반드시 왼쪽 자식 노드 하나만 갖도록 한다