[자료구조] 이진트리

 

트리

나무 형태를 뒤집은 것과 같은 형태의 자료구조

이미지 출처 : Wikipedia

• 루트 : 최상단 노드
• 리프 : 가장 끝 노드 
• 길이(length): 출발 노드에서 목적지 노드까지 거쳐야하는 가지 수
• 높이(height): 루트노드에서 가장 깊은 노드까지의 길이
• 부모 - 자식관계를 가지며, 같은 부모면 형제노드라고함

 

이진 트리(Binary tree)

최대 2개의 자식을 가질 수 있는 트리

• 포화 이진 트리(Full Binary Tree) : 리프노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리
• 완전 이진 트리(Complete Binary Tree) : 모든 노드가 왼쪽 자식부터 차근차근 채워진 트리
• 높이 균형 트리(Height Binary Tree) <-> 편향트리 : 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1이상 차이나지 않는 트리
• 많은 양의 노드를 낮은 높이에서 관리할 수 있어서 데이터 활용의 효율성이 높아짐
• 데이터 저장, 탐색 등의 다양한 목적에서 활용

 

이진 트리 구현

포인터를 이용하여 구현하면 효과적으로 데이터 관리 가능

 

이진트리의 순회

1. 전위 순회 : 자기 자신 출력 → 왼쪽 자식 방문 → 오른쪽 자식 방문
2. 중위 순회 : 왼쪽 자식 방문 → 자기 자신 출력 → 오른쪽 자식 방문
3. 후위 순회 : 왼쪽 자식 방문 → 오른쪽 자식 방문→ 자기 자신 출력

 

 

 

 

 

참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수