-
[자료구조] 자바로 트리(Tree) 구현하기, 트리의 탐색프로그래밍 2019. 8. 8. 01:27
- 자료구조의 일종
- 사이클이 없는 그래프
- 정점의 개수 V
- 간선의 개수 V-1
- 모두 연결되어있어야 함.
정점의 개수가 V, 간선의 개수 V-1이면 무조건 트리다=> X
연결되어 있어야함!
루트있는 트리 (Rooted Tree)
루트가 있는 트리
parent = 자식 Children을 하위에 가지는 노드.
parent가 없다 => root
Leaf Node = 트리의 가장 하위에 있는 노드
sibiling = 같은 부모를 가진다.
depth = root로부터의 거리 (root = 0)
Height = depth들 중에서 가장 큰 값.
Ancestor(조상), Descendant(자손)
(자신포함)
조상 : 자기 상위~root까지
자손 : 자기 하위 노드.
이진트리
자식을 최대 2개만 가지고 있는 트리
<트리의 표현>
- 트리는 그래프이기 때문에, 그래프의 표현과 같은 방식으로 저장가능
- 또는
- 트리의 모든 노드는 부모를 하나 또는 0개만 가지기 때문에 부모만 저장하는 방식으로도 트리를 저장할 수 있다.
- 혹은 이진 트리의 경우에는 트리를 저장하는 다른 방식을 이용할 수 있다. (배열 사용)
<트리의 순회>
- 트리의 모든 노드를 방문하는 순서이다.
- 그래프의 경우에는 DFS/BFS가 있었다.
- 트리에서도 사용가능! 하지만 트리에서만 사용가능한 3가지 방법이 있다.
- 프리오더 (전위 순회)
- 인오더 (중위 순회)
- 포스트오더 (후위 순회)
- 노드 방문을 언제 하냐의 차이로 나뉜다.
프리오더
노드방문
왼쪽 자식 노드를 루트로 하는 서브트리 프리오더
오른쪽 자식을 루트로 하는 서브트리 프리오더
인오더
왼쪽 자식 노드를 루트로 하는 서브 트리 인오더
포스트오더
왼쪽 자식 노드를 루트로 하는 서브 트리 포스트오더
오른쪽 자식 노드를 루트로 하는 서브 트리 포스트오더
노드방문
'프로그래밍' 카테고리의 다른 글
[Network] TCP Socket Programming - File Download [Server - Client] (0) 2019.11.13 [Docker] Docker(도커)+NodeJs(Sequelize)+Mysql 연동하기 / Docker-Compose 구성 및 Docker-Compose 순서 설정. (0) 2019.11.11 [자료구조] 이진탐색트리(Binary Search Tree, BST)의 시간복잡도 (0) 2019.08.14 [자료구조] JAVA로 그래프(Graph)구현하기, BFS, DFS (0) 2019.08.07 [자료구조] Stack 구현하기 (0) 2019.08.03