6. 트리

트리

노드로 이루어진 자료구조

• 트리는 하나의 루트 노드를 갖는다.
• 루트 노드는 0개 이상의 자식 노드를 갖는다.
• 그 자식노드 또한 0개 이상의 자식노드를 갖는다.
• 트리에는 싸이클이 존재할 수 없다.
• 각 노드느 부모 노드로의 연결이 있을수도 없을수도 있다.
• 비선형 자료구조로 계층적 관계를 표현

 

기본 용어

• 노드 : 한 정보 아이템 + 다른 노드로 뻗어진 가지
• 차수 : 한 노드의 서브트리 수
  • 단말 노드 : 차수 = 0
  • 비단말노드 : 차수 != 0
• 형제 : 부모가 같은 노드
• 리프 노드 : 자식이 없는 노드
• 부모 <-> 자식
• 트리의 차수 : 그 트리의 노드의 최대 차수
• 조상 : 루트에서부터 그 노드에 이르는 경로상의 모든 노드
• 레벨
  • 루트 : 레벨 1
  • 자식 : 부모 + 1
• 트리의 높이, 깊이 : 최대 레벨

 

산술식

A + B

• 중위(inorder) : LVR
• 후위(postorder) : LRV
• 전위(preorder) : VLR

 

트리의 노드 구조

typedef struct node *treep;
typedef struct node
{
    int data;
    treep left, right;
}

 

중위 순회

void inorder(treep ptr)
{
    if(ptr)
    {
        inorder(ptr -> left);
        printf("%d", ptr -> data);
        inorder(ptr -> right);
    }
}

 

전위 순회

void preorder(treep ptr)
{
    if(ptr)
    {
        printf("%d", ptr -> data);
        preorder(ptr -> left);
        preorder(ptr -> right);
    }
}

 

후위 순회

void postorder(treep ptr)
{
    if(ptr)
    {
        postorder(ptr -> left);
        postorder(ptr -> right);
        printf("%d", ptr -> data;
    }
}

 

승자 트리

패자 트리

 

이진 트리

각 노드가 최대 두 개의 자식 노드를 갖는 트리

포화 이진 트리 (Full Binary Tree)

마지막 레벨까지 모든 노드가 2개의 자식을 갖는 트리

• 깊이 : K
• 노드 수 : 2^K - 1

완전 이진 트리(Complete Binary Tree)

노드 삽입 시 왼쪽부터 차례대로 추가하는 이진 트리

포화 이진 트리의 leaf 노드 들의 오른쪽부터 제거하여 얻어진 트리

• 레벨 i에서 최대 노드 수 : 2^(i-1)
• 트리의 최대 노드 수 (깊이,높이 = K) : 2^K - 1