밍의 기록들😉

[트리] 트리의 표현 본문

자료구조, 알고리즘/기본다지기

[트리] 트리의 표현

민쓰 2018. 9. 9. 21:54

트리의 표현


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

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



이진 트리

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


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





* 백준 알고리즘 참고


0 Comments
댓글쓰기 폼