이진트리

이진트리 binary tree

 

각 노드의 자식 노드(차수)의 개수가 2개 이하로 구성되어 있는 트리

 

- 평향 이진 트리

노드들이 한쪽으로 편향되어 생성된 이진 트리

- 포화 이진 트리

트리의 높이가 모두 일정하며, 리프 노트가 꽉 찬 이진 트리

- 완전 이진 트리

마지막 level을 제외하고 완전하게 노드들이 채워지고, 마지막 level은 왼쪽부터 채워진 트리

---

트리의 노드와 리스트의 인덱스 사이 상관관계

이동 목표 노드	인덱스 연산	제약 조건 (n=노드개수)
루트 노드	Index=1
부모 노드	Index= index/2	현재 루트노드 아님
왼쪽 자식 노드	Index= index*2	Index*2<=n
오른쪽 자식 노드	Index= index*2+1	Index*2+1<=n