트리

트리

트리의 개념

• 트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 구조이다.
• 트리는 그래프의 한종류이다.(그래프와 다르게 사이클이 없다, 그래프는 사이클이 존재할 수 있음)
• 루트 노드, 부모-자식 개념이 존재한다.(그래프는 루트 노드 개념X, 부모-자식 개념X)
• 노드가 n개인 트리는 간선의 개수가 n-1이다
• 이진트리, 이진포화트리 (자식 노드가 최대 2개) 등이 존재한다.

 

트리 순회

출처 : https://withhamit.tistory.com/282

출처 : https://withhamit.tistory.com/282

• 전위 순회
  • 루트 - 왼쪽 - 오른쪽
  • C-B-A-E-D-F-G
  • C-B-A-1-2-3-E-D-4-5-F-6-G-7-8
• 중위 순회
  • 왼쪽 - 루트 - 오른쪽
  • A-B-C-D-E-F-G
  • 1-A-2-B-3-C-4-D-5-E-6-F-7-G-8
• 후위 순회
  • 왼쪽 - 오른쪽 - 루트
  • A-B-D-G-F-E-C
  • 1-2-A-3-B-4-5-D-6-7-8-G-F-E-C