[자료구조] 03 트리

▶ 트리 (Tree)

: 계층적 관계를 표현하는 자료구조

 

 

▶ 용어

노드 (Node)	트리의 구성요소
간선 (Edge)	노드와 노드를 연결하는 연결선
루트 노드 (Root Node)	트리 구조에서 최상위에 존재하는 노드
단말 노드 (Terminal Node)	아래로 또는 다른 노드가 연결되어 있지 않는 노드
내부 노드 (Internal Node)	단말 노드를 제외한 모든 노드
부모 노드 (Parent Node)	특정 노드의 상위 노드
자식 노드 (Child Node)	특정 노드의 하위 노드
형제 노드 (Sibling Node)	같은 부모 노드를 둔 노드
조상 노드 (Ancestor)	특정 노드 기준 위로 모든 노드
후손 노드 (Descendant)	특정 노드 기준 아래로 모든 노드
레벨 (Level)	트리의 루트노트를 0으로 시작하여 각 층별로 숫자를 매긴 것
높이 (Height)	트리의 최고 레벨

 

 

▶ 이진 트리 (Binary Tree)

: 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.

: 나뉘어진 두 서브 트리도 모두 이진 트리이어야 한다. (재귀적)

 

 

▶ 서브 트리 (Sub Tree)

: 큰 트리에 속하는 작은 트리

 

 

▶ 포화 이진 트리 (Full Binary Tree)

: 모든 레벨이 꽉 찬 이진 트리

 

 

▶ 완전 이진 트리 (Complete Binary Tree)

: 모든 레벨이 꽉 찬 상태는 아니지만, 위에서 아래로, 그리고 왼쪽에서 오른쪽의 순서대로 노드가 채워진 이진 트리

 

 

▶ 배열 기반 이진 트리

: 트리 완성 후 탐색을 빈번하게 하는 경우 구현

: 따라서 보통 연결 리스트 기반 이진 트리로 구현

 

 

▶ 이진 트리의 순회 (Traversal)

전위 순회 (Preorder Traversal)	루트 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드
중위 순회 (Inorder Traversal)	왼쪽 자식 노드 → 루트 노드 → 오른쪽 자식 노드
후위 순회 (Postorder Traversal)	왼쪽 자식 노드 → 오른쪽 자식 노드 → 루트 노드