트리

트리 정의

• 데이터의 상-하 관계를 저장하는 자료 구조
• 상하관계 = 계층적관계
• 배열, 링크드리스트는 선형적 자료 구조를 이루기에 부적합

트리 구성

• 트리 노드: 데이터 및 자식 노드 레퍼런스로 구성
  
• A노드 = 루트 노드
• B, C노드 = 형제 노드
• B, C노드와 같이 자식 노드가 없는 경우 = 리프 노드

트리 종류

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

이진 트리 구현(by python)

• 구현 대상
  

• 구현 내용
  

트리 순회

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

트리 순회 종류

1. pre-order 순회

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

• 구현 대상
  

2. post-order 순회

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

• 구현 대상
  

3. in-order 순회

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

• 구현대상