자료구조 | Ch02. Binary Tree

1. Binary Tree란?

Binary Tree는 모든 node가 2개 이하의 child node를 가지고 있는 tree이다. (모든 node의 degree <= 2)

Binary Tree도 여러 종류가 있다.

• A Full Binary Tree : 모든 node의 child node가 2개 또는 0개 인 tree이다.
• A Complete Binary Tree : 마지막 level을 제외한 모든 level이 완전히 채워진 Tree를 말한다.

오른쪽 그림은 complete binary Tree 이고, 왼쪽 그림은 왼쪽 node부터 채우지 않아서 complete binary tree가 아니다. 

 

그럼 binary tree의 특성은 무엇이 있을까?

 

Binary Tree는 leaf node가 아닌 모든 노드의 degree는 1또는 2여야 한다.

트리의 i - level에 있는 노드의 최대 갯수는 2^(i-1)이다. 예를 들어 level 3에 들어갈 수 있는 최대 노드의 수는 4(2^2)이다.

h-height인 tree의 전체 노드의 최대 갯수는 2^h - 1이다. 예를 들어 height 3인 tree의 전체 노드의 최댓값은 7(2^3 -1)이다.

 

2. Converting a General Tree into a Binary Tree

General Tree의 다양한 degree는 node를 읽거나, 지우거나, 삽입하는데 어렵다. 때문에 General Tree를 Binary Tree로 변환하여 사용하면 더욱 편리하게 사용할 수 있다. 이때 우린 "Leftmost Child - Right Sibilings" (LCRS)를 사용한다.

 

그럼 일반 Tree를 Binary Tree로 변환해보자.

아래 Tree는 한 paraent node에 3개의 child nodes가 있는 General Tree이다. 이를 Binary Tree로 변환하기 위해 가장 왼쪽에 있는 child를 제외한 다른 sibiling nodes는 parent node와의 연결을 끊고 sibiling끼리 연결한다.

 

위 처럼 LCRS를 이용하여 node를 연결 하였으면 right sibiling을 right child로 만든다.

알고리즘 정리:

General Tree의 root는 binary Tree의 root이다.

1-depth의 node에서 left-most node를 left child로 만든다.

만약 left child가 없으면 right sibiling를 right child node로 만든다.

위 과정을 전체 general tree에서 반복한다.

 

>> General Tree를 Binary Tree로 옮기는 과정에서 

• 모든 node는 포함된다.
• node의 상대적 level관계는 보존되지 않는다.
  ex) Level of E > Level of C  ---->  Level of E == Level of C
• parent-decendant 관계는 보존된다
  ex) node H는 node D의 descendant ---->  node H는 node D의 descendant

3. Coding in C

각각 노드는 structure로 만든다. node의 key의 데이터 타입은 상황에 따라 변경할 수 있고 한 node에 left_child와 right_child의 node를 가리킬 수 있도록 pointer로 선언해준다.

typedef struct node{
	int key; // data_type
    struct node* left_child;
    struct node* right_child;
    };

Inorder Traversal

void inorder(struct node* ptr)
{
	if(ptr)
    {	
    	inorder(ptr->left_child);
        visit node;
    	inorder(ptr->right_child);
    }
}

left child -> root -> right child 순회로 left, right child node가 NULL일때 조건문을 수행하지 않고 return된다.

Preorder Traversal

void preorder(struct node* ptr)
{
	if(ptr)
    {	
    	visit node;
    	preorder(ptr->left_child);
    	preorder(ptr->right_child);
    }
}

root -> left child -> right child 순회로 left, right child node가 NULL일때 조건문을 수행하지 않고 return된다.

Postorder Traversal

void postorder(struct node* ptr)
{
	if(ptr)
    {	
    	postorder(ptr->left_child);
    	postorder(ptr->right_child);
        visit node;
    }
}

left child -> right child -> root 순회로 left, right child node가 NULL일때 조건문을 수행하지 않고 return된다.