자료구조

전위 순회는 루트-왼쪽-오른쪽 중위 순회는 왼쪽-루트-오른쪽 후위 순회는 왼쪽-오른쪽-루트 위와 같은 순서로 트리의 노드를 방문하여 출력하는 문제이다. 이진트리이기 때문에 왼쪽, 오른쪽의 노드만을 가지며 이를 구현하는 class를 만들어 활용하면 문제를 쉽게 풀 수 있다. 다음은 Java로 작성한 코드이다. import java.util.ArrayList; import java.util.Iterator; import java.util.Scanner; public class traversal { static class node{ String value; String left; String right; public node(String v, String l, String r) { value = v; left..

트리(Tree)란? 트리란 그래프의 일종으로, 비순환적인 그래프를 말한다. 즉, 사이클이 없는 그래프를 트리라고 한다. 사이클이 존재하지 않아 모습이 나무를 닮아 트리라는 이름이 붙여졌다. 노드가 n 개라면 간선 n-1개로 이루어진 그래프이다. 이 특징 또한 사이클이 없기 때문에 성립한다. 트리 기본 용어 리프(leaf) 이웃한 노드가 하나만 있는 노드를 말한다. 나무 중 제일 끝에 위치한 나뭇잎과 같이 제일 끝에 있는 노드를 의미한다. 루트(root) 제일 위에 위치한 노드라고 생각하면 된다. 나무의 시작인 뿌리와 같이 트리의 시작으로 설정한 노드이다. 부모(parent) 노드 어떠한 노드보다 위에 위치하며 루트 쪽에 가까이 위치한 노드를 의미한다. 자식(child) 노드 어떠한 노드보다 아래에 위치하..

그래프의 표현 그래프를 표현하는 방법에는 여러 가지가 있다. 그래프의 크기가 어느 정도인지, 그리고 그래프를 어떻게 처리하는지에 따라 알맞은 자료 구조가 결정된다. 인접 리스트 인접 리스트(Adgacency list) 표현법은 그래프의 각 노드 x에 대한 인접 리스트, 즉 x에서 출발하는 간선이 있는 노드의 리스트를 관리한다. 인접 리스트는 그래프를 나타내는 가장 대중적인 방법이다. 인접 리스트를 ArrayList를 이중으로 이용하여 구현할 수있다. import java.util.ArrayList; public class GraphBasic { public static void main(String[] args) { ArrayList adj = new ArrayList(); for(int i = 0 ; ..

그래프(Graph)란? 그래프는 노드(node, 혹은 정점(vertex))와 그들을 잇는 간선(edge)으로 구성되어 있다. 경로(path)는 한 노드에서 그래프의 간선을 지나 다른 노드까지 가는 길을 의미한다. 경로의 길이는 경로에 포함된 간서의 개수이다. 예를 들어 1번 노드에서 5번 노드로 가는 길이가 3인 경로( 1 -> 3 -> 4 -> 5)가 나와 있다. 사이클(Cycle)은 처음 노드와 마지막 노드가 같은 경로를 의미한다. 예를 들어 1 -> 3 -> 4 -> 1로 구성된 사이클이 존재한다. 그래프의 모든 노드 간에 경로가 있는 경우를 연결 그래프(connected graph)라고 한다. 연결 그래프 연결 그래프가 아님 그래프의 연결된 부분을 컴포넌트(component)라고 표현한다. 연결 ..