트리

 

트리

• 계층적 구조가 있는 자료구조
• 계층적 관계가 있는 데이터를 컴퓨터에서 사용
• 컴퓨터과학의 다양한 문제 기발하게 해결
• 흔히 사용하는 여러 추상 자료형 구현

 

이진트리

• 각노가 최대 2개의 자식 노드를 가질수있는 트리

 

이진 트리 종류

 

정 이진 트리 (full binary tree)

• 2개 or 0개의 노드를 가지는 트리

완전 이진 트리 (complete binary tree)

• 마지막 레벨을 제외한 모든 레벨이 차있어야하며
• 마지막 레벨은 왼쪽에서 오른쪽으로 차있음
• 완전 이진 트리의 높이 O(lg(n))

포화 이진 트리 (perfect binary tree)

• 모든 트리 처럼 모든 레벨이 빠짐없이 다 노드로 채워져있는 이진트리
• 높이나 노드수 둘중 하나만 알아도 다른 하나의 값을 알 수있다.

 

트리 순회

 

순회 : 자료구조에 저장된 모든 데이터를 도는 것

 

순회 기본 동작들

• 재귀적으로 왼쪽 부분 트리 순회
• 재귀적으로 오른쪽 부분 트리 순회
• 현재 노드 데이터를 출력한다.

 

Pre-Order

재귀로 순회하기 전에 출력하는 순회 방법

• 현재 노드 데이터를 출력
• 재귀적으로 왼쪽 부분 트리 순회
• 재귀적으로 오른쪽 부분 트리 순회

 

Post-Order

부분트리 순회 후에 현재 노드 출력

• 재귀적으로 왼쪽 부분 트리 순회
• 재귀적으로 오른쪽 부분 트리 순회
• 현재 노드 데이터를 출력

 

In-Order

부분트리 순회 사이에 현재 노드 출력

• 재귀적으로 왼쪽 부분 트리 순회
• 현재 노드 데이터를 출력
• 재귀적으로 오른쪽 부분 트리 순회

 

 

트리를 순회 하면 노드들 사이에 선형적 순서를 만들 수있다.

⇒ 즉, 선형적 관계를 사용할 수있다.