Binary Tree를 1차원 배열을 사용해서 구성하기

문득 시간이 좀 남아서, heap sort 를 잠시 코딩했다가, binary tree와 1차원 배열사용해서 구성하는 방법을 알아보겠습니다.

Binary Tree는 1개의 parent 에 2개의 child 가 존재하는 트리입니다.

따라서, 이 binary tree 를 아래와 같이 BinaryTreeNode로 구현할 수 도 있습니다.

public class BinaryTreeNode {
    public BinaryTreeNode mLeftNode;
    public BinaryTreeNode mRightNode;
    public int data;
}

하지만, Binary에 착안해서, Binary Tree를 1차원 배열을 사용해서 구성할 수 도 있습니다.

배열에서 parent 의 index 가 i 라고 할 때,
left child i*2 +1
right child i*2 +2

이런 관계가 성립합니다.

http://mishadoff.com/blog/dfs-on-binary-tree-array/ ← 여기에 참 잘 설명 되어 있네요.

이렇게 배열의 인덱스를 사용해서, binary tree를 구성할 수 있으면, tree를 탐색 할 때, 같은 depth에 있는 node 방문하기도 쉽게 가능합니다. 이러면 BFS 나 DFS 에서 트리를 탐색하는 코드를 작성하기가 편해집니다.