[자료구조] 10강 트리, 이진트리, 순회, 응용, 스레드 이진트리, 이진 변환

* 이진 트리

 

이진 트리는 모든 노드가 정확하게 두 서브 트리를 가지고 있는 트리로 왼쪽 서브 트리와 오른쪽 서브 트리를 분명하게 구별할 수 있는 트리이다.

종류에는 완전이진트리, 포화이진트리, 편향이진트리 등이 있다.

이진트리의 주요 성질은 레벨 I의 최대 노드 수는 2i+1개 이고 높이가 h인 이진 트리의 최대 노드 수는 2h+1-1개이다.

 

완전 이진 트리는 높이가 h이고 노드 수가 n인 이진 트리에서 노드의 레벨 순서 번호들의 각 위치가 포화 이진 트리 번호 1에서 n까지 모두 일치하는 트리

포화 이진 트리는 높이가 h이고 노드 수가 2h+1-1인 이진 트리로 트리의 높이에 모든 자식 노드들이 채워진 트리를 의미

편향 이진 트리는 루트 노드를 기준으로 자식 노드가 한쪽 방향에만 존재하는 트리

 

* 이진 트리의 표현 방법

 

이진 트리의 표현 방법으로 일차원 배열과 연결리스트로 표현하는 방법이 있다.

일차원 배열로 표현하는 방법은 완전 이진 트리의 번호를 배열의 인덱스로 사용하여 나타낸다.

위에서 아래로, 왼쪽에서 오른쪽으로 각 노드 마다 인덱스를 순차적으로 부여

인덱스 0은 실제로 사용되지 않고 인덱스 1번부터 루트 노드를 시작으로 인덱스 번호에 맞게 순서대로 배열에 저장

편향 이진 트리의 순차 표현의 경우에는 일차원 배열로 나타낼 경우 공간 낭비가 심하다.

트리를 일차원 배열로의 표현하는 경우는 완전 이진 트리 외에는 저장 공간의 낭비가 심하기 때문에 트리의 또 다른 표현 방법인 연결 리스트를 사용한다. (Left Data, Right)로 표현하여 왼쪽 오른쪽 서브 트리를 가리키는 링크값을 저장, 자식 노드가 없을 경우 null값을 가진다)

 

* 이진 트리 순회

 

이진 트리에서 각 노드를 차례로 방문하는 것을 순회라고 한다. 트리의 노드가 n개 일 때 각 노드들을 순회하는 경우의 수는 n!의 가지이다.

노드를 순회할 때 방문하는 순서에 따라 중위(inorder)순회, 후위(postorder)순회, 전위(preorder)순회가 있다.

 

중위 순회

중위 순회는 왼쪽 서브 트리, 루트 노드와 오른쪽 서브 트리의 순으로 방문한다.

 

2.후위 순회

후위 순회는 왼쪽 서브 트리, 오른쪽 서브 트리와 루트 노드 순으로 방문한다.

 

3. 전위 순회

전회 순회는 자기 자신을 먼저 방문한 후 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 방문한다.

 

* 이진 트리의 응용

 

이진 트리에 의한 정렬

주어진 리스트를 정렬하기 위한 방법으로 이진트리를 이용

입력 데이터ㄹ의 첫 번째 원소를 루트 노드로 하고 다음 원소부터 각 노드와 비교하여 정렬할 원소가 작으면 왼쪽 자식 노드로 삽입하고 정렬할 원소가 크면 오른쪽 자식 노드로 삽입한다.

이렇게 생성된 이진 트리가 중위 순회를 하게 되면 주어진 리스트가 오름차순으로 정렬된 순열을 얻을 수 있다.

 

2. 명제 논리

변수와 연산자로 이루어진 명제식을 이진 트리로 표현하여 최종 결과인 참이나 거짓을 결정 할 수 있다.

 

* 스레드 이진 트리

 

연결 리스트로 표현한 이진 트리의 문제점으로는 실제로 사용하는 링크 수보다 사용하지 않는 null링크가 더 많다는 것이다. 이러한 문제점으로 활용하는 트리로 스레드를 저장하는 스레드 이진 트리가 있다.

스레드는 트리의 어떤 다른 노드에 대한 포인터로 활용하여 널 링크로 낭비되는 경우를 줄이고자 생성된 트리이다. (주로 사용되는 용도는 트리를 순회하는 정보로 활용)

스레드의 이진 트리 생성 방법은 노드 P의 right가 null인 경우 중위 순회에서의 중위 후속자에 대한 포인터 값을 갖고, 노드 P의 left가 null인 경우에는 중위 순회에의 중위 선행자에 대한 포인터를 저장

 

* 트리의 이진 트리 변환

 

일반 트리를 이진 트리로 변환하는 이유는 일반 트리의 자식 노드 수가 가변이기 때문에 확정적인 자료구조로 선언하기 어렵기 때문이다.

일반 트리의 경우에는 이진 트리로 변환하여 표현하게 되면 효율적인 표현방법 찾기가 수월해진다.

일반 트리를 이진 트리로 변화하는 방법은 한 노드의 모든 자식들을 첫 번째 자식과 나머지 다음 형제 관계로 만드는 것이다.