서론
완전 이진트리(Complete Binary Tree)는 규칙적으로 모든 노드가 순차적으로 2개의 지식 노드를 갖는다. 따라서, 배열은 사용할 경우 배열의 모든 칸이 낭비없이 가득 차게 되어 구현하기 편한 배열을 주로 사용한다. 하지만 연결리스트(Linked List)를 사용해서 구현하려면 어떻게 해야할까? 생각보다 복잡하지 않다. 이 글에서는 방법만을 설명하도록 하겠다.
필요지식
- 완전이진트리란?
본론
완전이진트리를 구성함에 있어 가장 걸림돌이 되는 부분은 새로 노드를 삽입해야 할 때, 이를 "어디에" 삽입해야 될 지를 모른다는 것이다. 여러가지 방법이 있지만, 필자가 소개하는 방법은 큐(Queue)를 사용하는 방법이다.
바로 방법을 소개하도록 하겠다.
IF (Queue가 비어있을 경우)
(1) 첫 노드를 Queue에 넣는다.
Else
(2) Queue의 front 노드의 left child가 없다면 left child에 새 노드를 삽입한다.
(3) Queue의 front 노드의 left child가 있다면 right child에 새 노드를 삽입하고, front 노드를 Queue에서 삭제한다.
(4) Queue에 새 노드를 삽입한다.
그림으로 보면 이해가 더 빠르게 될 것이다 (A, B, C, D를 삽입하는 경우)
위의 그림을 보면 노드를 삽입해야 되는 노드는 Queue의 front에 항상 위치하게 된다. 이는 모든 노드가 Queue에 삽입되고, 2개의 자식 노드를 가지게 되면 Queue에서 삭제되기 때문에, 완전 이진트리 생성에 필요한 순서대로 Queue의 front에 위치하게 된다.
'자료구조' 카테고리의 다른 글
| [포인터 정리] 2차원 구조체포인터를 함수에 인자로 전달 / 링크드리스트 / 해시테이블 (0) | 2019.03.11 |
|---|---|
| 트리(Tree), 이진트리(Binary Tree) (0) | 2017.12.11 |
| [C언어] Stack 구현 코드 (0) | 2017.11.22 |
| 완전이진트리(Complete Binary Tree)란? (0) | 2017.11.17 |
| 이진트리(Binary Tree)란? - From 위키백과 (1) | 2017.11.17 |
개발자_무형