[자료구조] Binary Tree

Binary Tree는 ordered tree의 일종으로, 각 node가 최대 2개까지의 children을 가질 수 있는 tree이다. 이 때, 모든 node의 children 개수가 모두 0 또는 2이면 이 binary tree는 'proper'하다고 하고, 그렇지 않으면 'improper' 하다고 한다.

 

Binary Tree의 특징

모든 node의 children 갯수가 2 이하라는 특징 때문에, (nonempty) binary tree는 다음과 같은 특징을 지닌다.

 

1. 높이가 h일 때, 전체 노드의 갯수는 h+1 보다 크거나 같고 2^(h+1)-1 보다 작거나 같다. 전체 노드의 갯수가 h+1인 경우는 각 internal node가 단 하나의 child만을 가질 때, 전체 노드의 갯수가 2^(h+1)-1 개일 때는 모든 internal node가 2개의 children을 가지는 경우이다.

 

2. external node의 갯수는 1보다 크거나 같고 2^h 보다 작거나 같다.

 

3. internal node의 갯수는 h 보다 크거나 같고 2^h-1보다 작거나 같다. 1. 번에서 나온 값에 2. 에서 나온 값을 뺀 것이다. 

 

4. 모든 internal node가 2개의 children을 갖는 경우 높이는 log(n+1)-1, 모든 internal node가 1개의 child 만갖는 경우 높이는 log(n-1)이다. 

 

Binary Tree 구현

1. Linked List 이용

다음 정보를 가진 node들을 담은 linked list를 통해 구현한다.

- element

- parent

- left child

- right child

struct node
{
    int element;
    node *parent;
    node *leftChild;
    node *rightChild;
};

 

2. Array-based

다음 규칙을 통해 구현한다.

- root node의 index는 0이다.

- qth element의 left child는 2q+1 위치에 넣는다.

- qth element의 right child는 2q+2 위치에 넣는다.

 

Traversal

Binary Tree를 순회하는 방식이다. 

1. Preorder Traversal : root -> left -> right 순서로 순회

2. Postorder Traversal : left -> right -> root 순서로 순회

3. Inorder Traversal : left -> root -> right 순서로 순회