[Data Structure] Tree

Tree

1. node 와 edge 로 연결한 계층형hierarchical자료구조
2. 하나의 노드로 이루어진 트리는 그 노드 자체가 트리이며, 루트이다

트리 용어

1. 차수 (degree): 노드가 가지고 있는 서브트리의 수
2. 리프, 단말: 차수가 0인 노드
3. 비단말: 차수가 0이 아닌 노드
4. 트리의 차수: 트리가 가지고 있는 노드 중에서 차수 중에서 최대 차수
5. 레벨
6. 트리의 높이: 트리의 최대 레벨

바이너리 트리 (이진 트리)

1. 모든 노드가 두개의 서브트리나 리프노드인 트리
2. 이진 트리 자체가 노드가 없는 공백 트리일 수 있음.
3. 레벨 k의 최대 노드수는 2^k
4. 높이가 h인 이진 트리의 최대노드 수 2^(h+1) - 1

편향 트리

포화 이진 트리

완전 이진 트리

완전 이진트리일까요

완전 이진트리 일차원 배열 표현

이진 트리의 인덱스 관계

일차원 배열 형태로 저장하면 노드의 삽입, 삭제시 많은 시간복잡도 야기

이진 트리 연결리스트 표현

이진 트리 연결 표현

중위 순회

전위 순회

후위 순회

일반트리 이진트리 변환

첫번째 자식 노드를 left 노드로 삼고 형제 노드를 right 노드로 연결한다.

제 경험상 항상 이렇지는 않았어요.