[트리] 트리의 표현

트리의 표현

• 트리는 그래피이기 때문에, 그래프의 표현과 같은 방식으로 저장할 수 있음
• 트리의 모든 노드는 부모를 하나 또는 0개만 가지기 때문에 부모만 저장하는 방식으로 저장 가능
• 부모가 0개인 경우는 트리의 루트인데, 이 경우 부모를 -1이나 0으로 처리하는 방식을 사용함

트리의 부모만 저장하는 방식

이진 트리

• 이진 트리의 경우는 배열로 표현 가능
• 부모의 노드가 x인 경우 
• 자식의 노드는 2*x, 2*x+1로 나타냄

• 이진 트리의 경우는 배열로 표현 가능
• A[i][0]에 i의 왼쪽 자식, A[i][1]에 i의 오른쪽 자식을 저장

* 백준 알고리즘 참고