Tree(이재용 부장님)

[자료구조 목차]

1. Tree 개요

 가. Tree 정의

 - 노드(Node)들이 나무 가지처럼 연결된 비선형 계층적 자료 구조

 - 아래 그림 같이 나무를 거꾸로 뒤집어 놓은 모양과 유사함

 나. Tree 특징

  - 그래프의 한 종류이며, '최소 연결 트리' 불림

  - 계층적 모델이고, DAG(Directed Acyclic Graphs, 방향성이 있는 비순환 그래프)의 한 종류

  - 노드가 N개인 트리는 항상 N-1 개의 간선(Edge)를 가짐

  - 루트에서 어떤 노드로 가는 경로는 유일함

  - 1개의 Root Node만 존재하며, 모든 자식 Node는 1개의 부모 노드만 가짐

 

2. Tree 구성도 및 구성요소

 가. Tree 구성도

 나.Tree 구성 요소 설명

구성 요소	설 명
루트 노드(Root Node)	- 부모가 없는 노드, 트리는 하나의 루트 노드만 가짐
단말 노드(Leaf Node)	- 자식이 없는 노드, '말단 노드' 또는 '잎 노드'라고 함
내부 노드(Internal Node)	- 단말 노드가 아닌 노드
간선(Edge)	- 노드를 연결하는 선(Link, branch)
형제(Sibling)	- 같은 부모를 가지는 노드
노드의 크기	- 자신을 포함한 모든 자손 노드의 개수
노드의 깊이	- 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨	- 트리의 특정 깊이를 가지는 노드의 집합
노드의 차수	- 하위트리 개수/간선 수(degree) = 각 노드가 지닌 가지의 수
트리의 차수	- 트리의 최대 차수
트리의 높이	- 루트 노드에서 가장 깊숙히 있는 노드의 깊이

 

3. Tree 순회 방식