[자료구조] 이진 트리의 표현: 배열/연결리스트

이진트리의 표현으로는, 배열과 연결리스트를 들 수 있다.

 

1) 배열

 

우선 1차원 배열에 노드를 저장한다. 자신의 번호를 가진 인덱스 위치에 저장해둔다. 이 때 인덱스 0번은 사용하지 않고 비워두고, 인덱스 1번부터 루트 노드를 저장한다.

 

n개의 노드를 가진 트리는 부모와 자식 노드의 인덱스 관계임을 볼 수 있다. 따라서 parent(i) : [i/2] if i != 1이 되고, leftChild(i) : 2i if 2i<= n, rightChild(i) : 2i+1 if 2i + 1<= n이 된다.

 

2) 연결 리스트

 

단순연결리스트를 이용하여 이진트리를 표현한다. 

c코드로 작성하면 다음과 같이 진행된다.

 

typedef int BTData;

typedef struct BinaryTreeNode{

        BTData data;

        struct BinaryTreeNode *left, *right;

}

BinTree;

 

연결리스트로 트리를 구현할 시, 부모 노드로 가기 어려운 문제가 생긴다. 이는 parent field를 추가하여 해결 가능하다.