트리(Tree)

• 트리: 데이터 사이의 계층 관계를 나타내는 자료구조
  • 노드(node), 가지(edge)
  • 루트(root): 가장 윗부분에 위치하는 노드
  • 리프(leaf): 가장 아랫부분에 위치하는 노드 (=끝 노드, 바깥 노드)
  • 안쪽 노드(internal node): 리프를 제외한 노드
  • 자식(child), 부모(parent), 형제(sibling)
  • 조상(ancestor): 어떤 노드에서 가지로 연결된 위쪽 노드 모두
  • 자손(descendant): 어떤 노드에서 가지로 연결된 아래쪽 노드 모두
  • 레벨(level): 루트로부터 얼마나 떨어져 있는지에 대한 값. 루트는 0
  • 차수(degree): 노드가 갖는 자식의 수
  • 높이(height): 루트부터 가장 멀리 떨어진 리프까지의 거리
  • 널 트리(null tree): 노드, 가지가 없는 트리
  • 순서 트리(ordered tree): 현제 노드의 순서를 따지는 트리 <-> 무순서 트리

---

• 순서 트리 탐색

1. 너비 우선 탐색(Breadth-first Search): 낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 내려가는 검색

2. 깊이 우선 탐색(Depth-first Search): 루트에서 리프까지 내려가면서 검색. 리프에 도달하면 부모로 돌아간 후 다른 자식 노드로 내려감.

• 전위 순회(Preorder): 노드 -> 왼쪽 자식 -> 오른쪽 자식
• 중위 순회(Inorder): 왼쪽 자식 -> 노드 -> 오른쪽 자식
• 후위 순회(Postorder): 왼쪽 자식 -> 오른쪽 자식 -> 노드

---

• 이진 트리(Binary tree): 노드의 자식이 2명 이하인 트리
• 완전 이진 트리(Complete binary tree):
  1. 마지막 레벨을 제외한 레벨은 노드를 가득 채움
  2. 마지막 레벨은 왼쪽부터 오른쪽으로 노드를 채우되 반드시 끝까지 채울 필요는 없음
• 이진 검색 트리(Binary Search tree):
  1. 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작음
  2. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 큼
  3. 같은 키 값을 갖는 노드는 없음

---

이진검색트리 만들기

 

• 노드 구조체 BinNode

typedef struct __bnode {
    Member data;
    struct __bnode *left;
    struct __bnode *right;
} BinNode;

 

• AllocaBinNode 함수: 노드 동적 할당

static BinNode *AllocBinNode (void){
    return calloc(1, sizeof(BinNode));
}

 

• SetBinNode 함수: 노드 값 설정

static void SetBinNode(BinNode* n, const Member* x, const BinNode* left, const BinNode* right){
    n->data = *x;
    n->left = left;
    n->right = right;
}

 

• Search 함수: 키 값으로 검색

BinNode* Search(BinNode* p, const Member* x){
    int cond; //데이터를 비교한 compare함수의 반환값
    if(p == NULL) return NULL;
    else if((cond = MemberNocmp(x, &p->data)) == 0) return p;
    else if(cond < 0) Search(p->left, x);
    else Search(p->right, x);
}

 

• Add 함수: 노드 삽입

BinNode* Add(BinNode* p, const Member* x){
    int cond;
    if(p == NULL){
    	p = AllocBinNode();
        SetBinNode(p, x, NULL, NULL);
    }
    else if((cond = MemberNocmp(x, &p->data)) == 0)
    	printf("[오류] %d는 이미 등록되어 있습니다.\n", x->no);
    else if(cond < 0)
    	p->left = Add(p->left, x);
    else
    	p->right = Add(p->right, x);
        
    return p;
}

 

• Remove 함수: 노드 삭제

1.삭제할 노드 p에 대신 넣을 노드 next

        왼쪽 서브 트리가 있는 경우: 왼쪽 서브 트리에서 가장 큰 노드(가장 오른쪽 노드)

        왼쪽 서브 트리가 없는 경우: 오른쪽 자식 노드

2. 왼쪽 서브트리에서 찾은 경우 - next의 자식으로 기존 p의 자식을 붙임

3. p 자리에 next를 붙인 후 (p의 부모가 next를 가리키게 됨) p 삭제

 

/// 변수 root, p의 자료형이 BinNode**인 이유:

/// 루트만 있을 때 루트를 삭제하는 경우 루트 포인터를 널로 업데이트하기 때문

int Remove(BinNode **root, const Member* x){
    BinNode *next, *temp;
    BinNode **left;
    BInNode **p = root;
    
    while(1){ //데이터 값이 x인 노드 겁색
    	int cond;
        if(*p == NULL){
        	printf("[오류] %d는 등록되어 있지 않습니다.\n", x->no);
            return -1;
        }
        else if((cond = MemberNocmp(x, &(*p)->data)) == 0) break;
        else if(cond < 0)
        	p = &((*p)->left);
        else p = &(*p)->right);
    }
    
    if((*p)->left == NULL) next = (*p)->right; //왼쪽 자식이 없으면 오른쪽 자식
    else{
    	left = &(*p)->left);
        while((*left)->right != NULL) //왼쪽 서브 트리에서 가장 큰 값을 찾음(가장 오른쪽 값)
        	left = &(*left)->right;
        next = *left;
        *left = (*left)->left; //찾은 가장 큰 값 자리에 왼쪽 자식 노드를 복사(자식이 없으면 널값)
        
        next->left = (*p)->left; //찾은 값을 p자리에 넣음
        next->right = (*p)->right;
    }
    temp = *p;
    *p = next; //next를 p의 부모노드의 자식으로 붙임
    free(temp);
    
    return 0;
}

 

• PrintTree 함수: 모든 노드를 오름차순으로 출력 (중위 순회 방법)

void PrintTree (const BinNode* p){
    if(p != NULL) {
    	PrintTree(p->left); //현재 노드의 왼쪽 서브 트리로 이동
        PrintMember(&p->data); //가장 작은 값부터 노드 하나씩 데이터 값 출력
        PrintTree(p->right); //현재 노드의 오른쪽 서브 트리로 이동
    }
}

 

• FreeTree 함수: 모든 노드를 삭제 (후위 순회 방법)

void FreeTree (BinNode* p){
    if(p != NULL){
    	FreeTree(p->left);
        FreeTree(p->right);
        free(p);
    }
}