트리

• 트리 : 계층적인 구조를 나타내는 자료구조
  - 리스트, 스택, 큐 등은 선형 구조
• 트리는 부모-자식 관계의 노드들로 이루어짐

트리 용어

• 노드(Node) : 트리의 구성요소
• 루트(root) : 부모가 없는 노드
• 서브트리(subtree) : 하나의 노드와 그 노드들의 자손들로 이루어진 트리
• 단말노드(terminal node) : 자식이 없는 노드
• 비단말노드 : 적어도 하나의 자식을 가지는 노드
• 차수(degree) : 노드가 가지고 있는 자식 노드의 개수
• 레벨(level) : 트리의 각층의 번호
• 높이(height) : 트리의 최대 레벨

트리 종류

• 이진 트리
• 일반 트리

이진 트리 (binary tree)

이진 트리
- 모든 노드가 최대 2개의 서브 트리를 가지고 있는 트리
- 서브트리는 공집합일 수 있음

• 이진 트리의 노드에는 최대 2개까지의 자식 노드가 존재
• 모든 노드의 차수가 2 이하가 됨 -> 구현하기가 편리함
• 이진 트리에는 서브 트리간의 순서가 존재

이진 트리의 성질

• 노드의 개수가 n개이면 간선의 개수는 n-1

• 높이가 h인 이진 트리의 경우, 최소 h개의 노드를 가지며 최대 (2^h)-1개의 노드를 가짐

• n개의 노드를 가지는 이진 트리의 높이

이진 트리의 분류

• 포화 이진 트리 (full binary tree)
• 완전 이진 트리 (complete binary tree)
• 기타 이진 트리

이진 트리 표현 - 링크 표현법

링크 표현법 : 포인터를 이용해 부모노드가 자식노드를 가리키게 하는 방법

구현

링크의 구현

• 노드는 구조체로 표현
• 링크는 포인터로 표현

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct TreeNode{
	int data;
    struct TreeNode *left, *right;
}TreeNode

void main(){
	TreeNode *n1, *n2, *n3;
    
    n1 = (TreeNode *)malloc(sizeof(TreeNode));
    n2 = (TreeNode *)malloc(sizeof(TreeNode));
    n3 = (TreeNode *)malloc(sizeof(TreeNode));
    
    n1->data = 10;
    n1->left = n2;
    n1->rigth = n3;
    
    n2->data = 20;
    n2->left = NULL;
    n2->rigth = NULL;
    
    n3->data = 30;
    n3->left = NULL;
    n3->rigth = NULL;
}

---

이진 트리의 순회

순회
- 트라ㅣ의 노드들을 체계적으로 방문하는 것

3가지 순회방법

1. 전위 순회 (preorder traversal) : VLR
   • 자손노드보다 루트노드를 먼저 방문
2. 중위 순회 (inorder traversal) : LVR
   • 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문
3. 후위 순회 (postorder traveral) : LRV
   • 루트노드보다 자손을 먼저 방문

전위 순회 (preorder traversal)

루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리

preorder(TreeNode *root){
	if(root){
    	printf("%d", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

중위 순회 (inorder traversal)

왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리

inorder(TreeNode *root){
	if(root){
    	inorder(root->left);
        printf("%d", root->data);
        inorder(root->rigth);
    }
}

후위 순회 (postorder traveral)

왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트

postorder(TreeNode *root){
	if(root){
    	postorder(root->left);'
        postorder(root->rigth);
        printf("%d", root);
    }
}

레벨 순회

void level_order(TreeNode *root){
	QueueType q;
    init_queue(&q);
    if(ptr == NULL) return;
    equeue(&q, ptr);
    while(!is_empty(&q)){
    	ptr = dequeue(&q);
        printf(" [%d}] ", ptr->data);
        if(ptr->left)
        	enqueue(&q, ptr->left);
        if(ptr->right)
        	enqueue(&q, ptr->right);
   	}
}

이진탐색트리의 탐색

순환적인 탐색

TreeNode *searcH(TreeNode *node, int key){
	if( node == NULL)
    	return NULL;
    if( key == node->key)
    	return node;
    else if( key < node->key)
    	return search(node->left, key);
    else
    	return search(node->right, key);
}

반복적인 탐색

TreeNode *search(TreeNode *node, int key){
	while(node != NULL){
    	if( key == node->key)
        	return node;
        else if( key < node->key)
        	return search(node->left, key);
       	else
        	return search(node->right, key);
   	}
    return NULL;
}

삽입 연산

void insert_node(TreeNode **root, int key){
	TreeNode *p, *t;
    TreeNode *n;
    t = *root;
    p = NULL;
    
    while( t!= NULL ){
    	if( key == t->key )
        	return;
        p = t;
        if( key < t->key )
        	t = t->left;
        else
        	t = t->right;
    }
    
    n = (TreeNode *)malloc(sizeof(TreeNode));
    if( n == NULL )
    	return;
        
    n->key = key;
    n->left, n->right = NULL;
    
    if( p != NULL ){
    	if( key < p->key )
        	p->left = n;
        else
        	p->right = n;
   	else
    	*root = n;
}

삭제 연산

void delete_node(TreeNode **root, int key){
	TreeNode *p, *child, *succ, *succ_p, *t;
    p = NULL;
    t = *root;
    
    while( t != NULL && t->key != key ){
    	p = t;
        t = (key < t->key) ? t->left : t->right;
    }
    if( t == NULL ){
    	printf("key is not in the tree");
        return;
    }
    
    if( (t->left == NULL) && (t->right == NULL) ){
    	if( p != NULL){
        	if( p->left == t )
            	p->left = NULL;
            else
            	p->right = NULL;
        }
        else
        	*root = NULL;
    }
    else if( (t->left == NULL) || (t->right == NULL) ){
    	child = (t->left != NULL) ? t->left : t->right;
        if( p != NULL ){
        	if( p->left == t )
            	p->left = child;
            else
            	p->right = child;
       	}
        else
        	*root = child;
   	}
    else
    	succ_p = t;
        succ = t->right;
        
        while( succ->left != NULL ){
        	succ_p = succ;
            succ = succ->left;
        }
        if( succ_p->left == succ )
        	succ_p->left = succ->right;
        else
        	succ_p->right = succ->right;
            
        t->key = succ-key;
        t = succ;
    }
    tree(t);
}
        

순환적인 탐색

삽입 연산

TreeNode *new_node(int item){
	TreeNode *temp = (TreeNode *)malloc(sizeof(TreeNode));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

TreeNode *insert_node(TreeNode *node, int key){
	if( node == NULL )
    	return new_node(key);
    
    if( key < node->key )
    	node->left = insert_node(node->left, key);
    else if( key > node->key)
    	node->right = insert_node(node->right, key);
    return node;
}

삭제 연산

TreeNode *min_value_node(TreeNode *node){
	TreeNode *current = node;
   	
    while( current->left != NULL )
    	current = current->left;
    return current;
}

TreeNode *delete_node(TreeNode *root, int key){
	if( root == NULL )
    	return root;
    
    if( key < root->key )
    	root->left = delete_node(root->left, key);
   	else if( key > root->key )
    	root->right = delete_node(root->right, key);
    else{
    	if( root->left == NULL ){
        	TreeNode *temp = root->right;
            free(root);
            return temp;
       	}
        else if( root->right == NULL ){
        	TreeNode *temp = root->left;
            free(root);
            return temp;
        }
        TreeNode *temp = min_value_node(root->right);
        root->key = temp->key;
        root->right = delete_node(root->right, temp->key);
    }
 	return root;
}