자료구조 트리

트리의 정의

트리는 나무를 거꾸로 매달아 놓은 것의 모양을 띄는 데이터를 구조화한 것으로 검색의 편리함, 논리적 계층, 계급적 특성을 갖고 있다. 이는 데이터를 사용하는 목적에 따라 추상화한다. 

 

트리의 구성

• 노드 : 트리의 항목/트리에 저장되는 데이터의 묶음
• 부모노드와 자식노드 : 상하 계층구조가 있고 직접적으로 연결된 노드들로서 상위계층의 부모노드와 하위계층에 자식노드를 의미한다.
• 루트노드 : 트리의 최상위 노드(부모 노드가 없는)
• 서브트리 : 부모노드를 삭제하면 생기는 트리
• 잎노드 : 트리 맨 끝에 있으면서 자신의 서브트리를 갖지 않는 노드.(자식 노드가 없다)

진입/진출차수

• 루트노드 : 진입차수 = 0
• 루트노드를 제외한 모든 노드의 진입 차수 : 1
• 잎노드 : 진출 차수 = 0

내부 노드와 형제

• 내부 노드 : 루트, 잎이 아닌 노드 B , C , d, e, f, g
• 형제 노드 : 같은 부모를 갖는 노드들 (d, e)등

노드의 레벨 : 루트로부터 그 노드까지 이어진 선의 길이를 말한다. 깊이라고 생각하자.

1. 레벨 0 : A
2. 레벨 1 : A, B
3. 레벨 2 : d, e, f, g
4. 레벨 3 : h, i, j, k, l, m, n, o

트리의 깊이는 트리의 레벨에서 가장 큰 값에 1을 더한 것( 위의 표의 트리의 깊이는 4)

 

트리의 추상자료형

트리는 데이터의 계층관계, 포함 관계등을 나타내는 자료구조이기에 데이터는 매우 광범위하고 응용에 따라 다양하다.

트리 객체의 정의 : 루트 노드를 갖는 유한 리스트
연산
▷ Tree Creat( ) ::= 트리를 생성하고 루트 노드를 가리키는 포인터를 반환한다.
▷ Destroy(Tree) ::= 더 이상 사용하지 않는 트리의 기억장소를 시스템에 반환한다.
▷ Tree Copy_Tree(Tree) ::= 트리를 복사하고 새로 생성한 트리의 루트노드를 가리키는 포인터를 반환한다.
▷ Insert(n) ::= 트리에 노드 n을 삽입한다.
▷ Delete( ) ::= 트리에서 노드를 삭제한다. 보통 재구성 단계를 포함한다.
▷ Search( ) ::= 트리에서 특정 키값을 갖는 노드를 찾는다. 찾으면 true 아니면 false를 반환한다.
▷ Traverse( ) ::= 트리를 순회하고 방문 순서대로 값을 반환한다.
▷ Root( ) ::= 루트 노드 값을 반환한다.
▷ Parent(n) ::= 노드 n의 부모(값이나 포인터)를 반환. n이 루트이면 오류를 반환한다.
▷ Children( ) ::= 노드 n의 자식(값 또는 포인터)를 반환. n이 잎이면 오류 반환
▷ IsRoot(n) ::= 노드 n이 루트이면 true 아니면 false를 반환한다.
▷ IsInternal(n) ::= 노드 n이 내부 노드이면 true 아니면 false를 반환한다.
▷ IsLeaf(n) ::= 노드 n이 잎이면true 아니면 false를 반환한다.
▷ IsEmpty( ) ::= 트리가 비어있으면 true아니면 false를 반환한다.
▷ Replace(n, m) ::= 노드 n을 노드 m으로 바꾼다.

이진트리

이진트리는 모든 노드의 차수가 2 이하인 트리이다.(진입과 진출하는 개수가 2 이하) 수학적으로 이진트리의 구성에 관한 이론을 정리하기 용이하고, 컴퓨터 내부에서도 구현하기도 효율적이다. 모든 노드가 2개 이하의 자식노드를 가지므로 일반성을 잃지 않고 오른쪽과 오니 쪽이라는 방향 개념을 부여할 수 있다. 하여 오른쪽 노드와 왼쪽 노드의 개념적 접근도 있다.

• 가득 찬 이진트리(포화이진트리) : 이진트리의 각 레벨에서 허용되는 최대 노드를 가지는 트리.
• 완전 이진트리의 정의 : 높이가 k인 이진트리가 0 레벨부터 k-2 레벨까지 모두 다 채우고 마지막 k-1 레벨에서 왼쪽과 오른쪽 잎노드들이 차례로 채워진 이진트리.
• 배열을 이용한 이진트리 구현은 트리가 완전 이진트리 또는 가득찬 이진트리인 경우 낭비되는 공간이 없어 효율적이지만 트리가 깊어질수록 기억장소 낭비가 많아진다. 
• 그렇기 때문에 포인터를 이용해 이진트리 구현하게 된다.

이진트리 연산

이진 트리의 순회 : 이진트리의 각 노드를 빠짐없이 중복 없이 한 번씩 모두 방문하는 것을 말한다.

 

전위 순회 PLR : 루트노드 - 왼쪽 자식노드 - 오른쪽 자식노드

A-B-d-h-i-e-j-k-c-f-i-m-g-n-o

중위순회 LPR : 왼쪽 자식노드  - 루트노드 -오른쪽 자식노드

h-d-i-B-j-e-k-A-l-f-m-c-n-g-o

후위 순회 LRP   : 왼쪽 자식노드 -오른쪽자식노드 -루트노드

h-i-d-j-l-k-e-B-l-m-f-n-o-g-c-

 

 

typedef struct node{
struct node *left;
char data;
struct node *right;
} node;
void preorder(node *root){ //전위 순회
if(root!= NULL){
printf("% d", root →data);
postorder(root → left);
postorder(root → right);
}}
viod preorder(node *root){ //중위 순회
if(root!= NULL){
inorder(root →lesf);
printf("% c", root → data);
inorder(root → right);
}}
void preorder(node *root){ //후위 순회
if(root!= NULL){
postorder(root → left);
postorder(root → right);
printf("% c", root → data);
}}

이진트리의 생성/삽입/삭제

일반적인 이진트리를 생성하는 것은 연결리스트 연을 사용한다. 첫 노드를 생성하고 루트노드가 되고 새로운 노드를 추가하려면 연결 리스트의 삽입 연산을 사용한다.

노드를 삭제할 때 삭제하려는 노드가 잎노드인 경우는 해당 노드를 가리키는 포인터를 NULL로 지정하면 됨 하지만 잎노드가 아닌 경우는 삭제하려는 노드의 자식노드에 대한 처리가 필요해진다. 이는 어떤 형식으로 할 찌는 프로그래머가 목적에 맞게 정할일이다.

 

일반트리를 이진트리로 변환

이진트리가 사용하기에 편리하기 때문에 자주 변환한다. 먼저 주어진 트리에 대해 각노드 형제를 연결한 후 각노드에 대하여 가장 왼쪽링크만 남기고 모두 제거한다. 그리고 반드시 왼쪽자식 하나만 가지도록 한다.