트리(tree)

● 트리란?

트리(tree)는 비선형 구조로서 나무와 비슷한 형태를 가졋다고 하여 트리란 이름이 붙여졌다.
족보나 조직도 등 계층 구조를 갖는 데이터를 표현하는데 매우 적합하다.

-노드 중에는 루트라고 하는 노드가 하나가 존재
-나머지 노드들은 분리집합으로 분리될 수 있으며, 이것들은 각각 하나의 트리이며 루트의 서브트리라고 한다.  (트리는 재귀적 성질을 갖는 대표적인 자료구조 )

 

① 차      수 : 어떤 노드의 서브트리의 수     A의 차수는 3 , E의 차수는 2
② 단말노드 : 차수가 0인 노드
③ 부      모 : 자신의 상위 레벨 노드
④ 자      식 : 하위 레벨에 연결된 노드
⑤ 형      제 : 부모가 같은 노드
⑥ 조      상 : 루트에서부터 그 노드에 이르는 경로상에 있는 모든 노드
⑦ 자      손 : 한 노드의 서브트리에 속한 모든 노드

● 이진 트리

연결 리스트를 사용한다면 한 개의 노드에는 그  차수만큼의 링크 필드가 필요하게 될 것이다.
그러나 각 노드마다 서로 다른 링크 필드의 수를 가지므로 복잡도가 증가하고, 하나의 노드 구조를 정의하면 쓰이지 않는 링크가 대다수이어서 기어 장소를 낭비하게 된다.
이를 위해 링크가 2개로 고정되도록 일반 트리는 이진 트리로 변경하여 사용하기도 하였다.

① 포화 이진 트리(정 이진 트리) : 트리를 구성하는 각 노드의 차수가 0이거나 정확히 2인 노드

 

 

② 완전 이진 트리(전 이진 트리) : 레벨이 같을 경우 왼쪽에서 오른쪽으로 번호를 붙이는 방법을 사용하여 순차적인 대응이 되는 트리     ↓→

 

 

● 중위 운행

중위 운행은 각 노드에서 왼쪽 서브트리를 모두 처리한 후 자신의 노드를 방문하고 오른쪽 서브트리를 처리하는 방식으로 운행한다.  ( NULL에 도달할 때까지 왼쪽 방향으로 이동한다. )

typedef struct tnode *tree_pointer
struct tnode {
    tree_pointer left_child;
    int data;
    right_child;
};

재귀 함수를 통해 구현
void inorder(tree_pointer ptr)
{
    if (ptr) {
        inorder(ptr -> left_child);
        printf("%d    ", ptr -> num);
        inorder(ptr -> right_child);
    }
}

● 전위 운행

전위 운행은 각 노드에서 자신의 노드를 먼저 처리하고 왼쪽 서브트리, 마지막으로 오른쪽 서브트리를 처리하는 방식으로 운행한다.

위와 순서만 변경
void preorder(tree_pointer ptr)
{
    if (ptr) {
        printf("%d    ", ptr -> num);
        inorder(ptr -> left_child);
        inorder(ptr -> right_child);
    }
}


● 후위 운행 

후위 운행은 각 노드에서 자신에 노드를 방문하기 전에 왼쪽 서브트리와 오른쪽 서브트리를 먼저 방문하여 처리하는 방식으로 운행한다.

위와 순서만 변경
void postorder(tree_pointer ptr)
{
    if (ptr) {
        inorder(ptr -> left_child);
        inorder(ptr -> right_child);
        printf("%d    ", ptr -> num);
    }
}

● 이진 탐색 트리

이진 탐색 트리는 이진 트리의 특수한 형태로 공백이 가능한 이진 트리이다.

① 모든 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않는다.
② 공백이 아닌 왼쪽 서브트리에 있는 키들은 그 서브트리의 루트의 키보다 작아야한다.
③ 공백이 아닌 오른쪽 서브트리에 있는 키들은 그 서브트리의 루트의 키보다 커야한다.
④ 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

● 이진 탐색 트리의 검색

tree_pointer search(tree_pointer root, int key)
{
    if (!root) return NULL;
    if (key == root -> data) return root;
    if (key < root -> data )
        return search(root -> left_child, key);
    return search(root -> right_child, key);
}

● 이진 탐색 트리의 검색2

tree_pointer search(tree_pointer tree, int key)
{
    while(tree) {
        if (key == root -> data) return tree;
        if (key < tree -> data )
            tree = tree -> left_child;
        else
            tree = tree -> right_child;
    }
    return NULL;      
}

● 이진 탐색 트리를 이용한 명함관리 프로그램 ( 발코딩 )