참고
Tree traversal
NOTE
Tree를 순회(Traversal)하는 방법은 여러가지가 존재한다!
•
대표적으로 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)이 존재하며 깊이 우선 탐색은 전위/중위/후위 순회로 구분된다.
DFS(깊이 우선 탐색)
NOTE
한쪽 벽을 정해 그 벽을 계속 따라가는 방식이다!
가장 깊은곳까지 들어간다음 옆으로 간다위
전위 순회
NOTE
현재 노드를 먼저 방문하고, 그 다음에 왼쪽과 오른쪽 하위 트리를 차례로 탐색하는 방법이다!
A
/ \
B C
/ \ / \
D E F G
Java
복사
순회순서 ⇒ A, B, D, E, C, F, G (정렬된 순서를 볼 수 있다!)
traversePreorder(Node node) {
if(node == null) return null;
node.visited = true;
traverseInOrder(node.left);
traverseInOrder(node.right);
}
Java
복사
•
사용 사례
◦
이진 탐색트리를 중위 순회하면 정렬된 순서의 출력을 얻을 수 있다.
중위 순회
NOTE
현재 노드를 왼쪽 하위 트리를 모두 방문한 후, 그리고 오른쪽 하위 트리를 방문하기 전에 차례로 확인하는 방법이다!
A
/ \
B C
/ \ / \
D E F G
Java
복사
순회순서 ⇒ D, B, E, A, F, C, G
traverseInorder(Node node) {
if(node == null) return null;
traverseInOrder(node.left);
node.visited = true;
traverseInOrder(node.right);
}
Java
복사
•
사용 사례
◦
표현식 트리 : 수학 표현식이나 논리 표현식을 전위 표기법으로 출력할 때 사용한다.
◦
트리의 복사 : 트리의 구조 복사
◦
파일 시스템 : 디렉토리와 하위 디렉토리, 파일을 탐색할 때 사용한다.
후위 순회
NOTE
왼쪽과 오른쪽 하위 트리를 모두 방문한 후에 마지막으로 현재 노드를 방문하는 방법이다!
A
/ \
B C
/ \ / \
D E F G
Java
복사
순회순서 ⇒ D, E, B, F, G, C, A
traverseInorder(Node node) {
if(node == null) return null;
traverseInOrder(node.left);
traverseInOrder(node.right);
node.visited = true;
}
Java
복사
•
사용 사례
◦
표현식 트리 : 후위 표기법으로 수학 표현식을 출력할 때 사용한다.
◦
트리 삭제 : 트리의 모든 노드를 안전하게 삭제하기 위해 사용한다.
◦
종속성 해결 : 하위 노드가 상위 노드에 대한 어떤 종속성을 가질 때, 후위 순회를 사용해서 하위 노드부터 처리할 수 있다/.
DFS 구현 - Stack
NOTE
class Node {
public int data;
public boolean visited;
ArrayList<Node> children;
public Node(char value) {
this.value = value;
this.visited = false;
this.children = new ArrayList<>();
}
}
Java
복사
// 오른쪽 하위 트리부터 탐색
public void dfs(Node node) {
Stack<Node> stack = new Stack<>();
stack.push(node);
while(!stack.empty()) {
Node currentNode = stack.pop();
currentNode.visited = true;
// 정방향 검색
for (Node child: currentNode.children) {
stack.push(child);
}
}
}
// 왼쪽 하위 트리부터 탐색
public void dfs(Node node) {
Stack<Node> stack = new Stack<>();
stack.push(node);
while(!stack.empty()) {
Node currentNode = stack.pop();
currentNode.visited = true;
// 역순 검색
for (int i = currentNode.children.size() - 1; i >= 0; i--) {
stack.push(currentNode.children.get(i));
}
}
}
Java
복사
DFS 구현 - 재귀
NOTE
public static void dfs(Node node) {
node.visited = true;
for (Node child: node.children) {
if (!child.visited) dfs(child);
}
}
Java
복사
재귀방식이 훨씬 구현하기 좋다..
BFS(너비 우선 탐색)
NOTE
넓게 넓게 둘러보자는 방식의 탐색!
가장 가까운거부터 탐색한다.
•
낮은 레벨 노드에서 시작해, 왼쪽에서 오른쪽 방향으로 순차적으로 방문하는 방법이다.
•
최단 경로를 찾기에 적합한 탐색 방법이다.
BFS 구현
NOTE
Queue를 사용한다!
class Node {
public int data;
public boolean visited;
ArrayList<Node> children;
public Node(char value) {
this.value = value;
this.visited = false;
this.children = new ArrayList<>();
}
}
Java
복사
public void bfs(Node node) {
Queue<Node> queue = new Queue<>();
queue.add(node);
while(!stack.empty()) {
Node currentNode = queue.remove();
currentNode.visited = true;
for (Node child: currentNode.children) {
queue.add(child);
}
}
}
Java
복사