[자료구조]트리

트리

비선형 자료구조
계층적 관계를 표현하는 자료구조

• 노드
• 간선
• 루트 노드
• 단말 노드
• 내부 노드

이진 트리

• 루트 노드를 중심으로 두 개의 서브 트리
• 나뉘어진 두 서브 트리도 모두 이진 트리

포화 이진 트리
모든 레벨이 꽉 찬 이진 트리

완전 이진 트리
왼쪽에서 오른쪽으로 순서대로 빈틈없이 채워진 이진트리

이진 트리 구현

배열 기반과 연결 리스트 기반이 있다

typescript

이진 트리의 순회

루트 노드를 기준으로 순회한다

• 전위 순회(Preorder Traversal) : 루트 노트를 먼저 루트 - 왼쪽 - 오른쪽
• 중위 순회(Inorder Traversal) : 루트 노드를 중간 왼쪽 - 루트 - 오른쪽
• 후위 순회(Postorder Traversal) : 루트 노드를 마지막에 왼쪽 - 오른쪽 - 루트

순회 구현

이진 트리는 이진 트리가 모여있는 형태이기 때문에 재귀적으로 순회하면 된다

typescript
먼저 중위 순회를 예로 들자면

console.log로 data 출력하는 것으로 방문을 했다고 표현 할 수 있지만
방문 목적은 다를 수 있으니 함수를 인자로 넣어 표현 하고 싶은 형태로 바꿀 수 있다

이진트리 코드에서 추가된 코드
typescript