[이진트리] 이진트리의 구현

구조체 포인터를 활용한 구현

전에 Left-Child Right-Sibling 방식을 다룬 적이 있습니다.
이 방법은 각 노드의 차수가 다양할 때 생기는 문제를 해결해주었습니다.
하지만, 이진트리는 차수가 0, 1, 2 중 하나이기 때문에 LCRS 방식을 쓰지 않아도 비교적 간단하게 나타낼 수 있습니다.

간단하게 말하자면, 각각 왼쪽 자식과 오른쪽 자식을 가리키는 포인터를 만든 뒤, 자식이 없으면 그 포인터를 nullptr로 바꿔주면 됩니다.

1 2 3 4

typedef struct _node{ int data; struct _node *left, *right; }Node;

이런 식으로 구현하면 됩니다.

구조체를 싫어하는 분들을 위한 또 다른 구현 방법이 있습니다.

배열을 활용한 구현

바로 일차원배열을 활용하는 방법입니다.

이런 식으로 번호를 붙여봅시다. 노드를 몇 개 제거해도 됩니다.

두 사진을 보면서 한 가지 사실을 도출해낼 수 있습니다.
k노드의 왼쪽 자식은 2 * k이고, 오른쪽 자식은 2 * k + 1입니다.
k노드의 부모는 k / 2를 버림 한 값인데, c언어에서는 정수끼리의 나눗셈을 버림해서 나타내기 때문에 k노드의 부모는 k / 2 입니다.

이렇게 두 가지 방법으로 이진 트리를 구현하는 법을 다뤘습니다.
보통은 구조체로 구현을 하지만, 만약 이진트리가 완전/포화 이진 트리에 가까울 때에는 일차원 배열을 고려해보는 것도 좋을 듯 합니다.
다음 글에서는 이진 트리의 순회에 대해 다룰 것 입니다.