Tree Search Algorithm
특정 목적을 위해 트리의 모든 노드를 한번씩 방문하는 것을 트리 순회라고한다.
트리 구조는 계층적 구조이기 때문에, 모든 노드를 순회하는 방법엔 크게 3가지가 있다.
(순회 방식과는 논외로, 트리 구조에서 노드를 순차적으로 조회할 때는 항상 왼쪽부터 오른쪽 순서로 한다. )
- 전위 순회 (preorder traverse)
가장 먼저 루트 노드부터 방문한다. 루트에서부터 시작해서 왼쪽의 노드들을 차례대로 방문한다.
왼쪽 노드 탐색이 끝나면 오른쪽을 탐색한다.
정리하면, 부모 노드가 제일 먼저 방문되는 순회 방식이다.
전위 순회는 주로 트리를 복사할 때 사용한다.
class Node {
String data;
Node left;
Node right;
public Node getLeft() {
return left;
}
public String getData() {
return data;
}
public Node getRight() {
return right;
}
}
public ArrayList<String> preOrder(Node node, ArrayList<String> list) {
if (node != null) {
list.add(node.getData());
list = preOrder(node.getLeft(), list);
list = preOrder(node.getRight(), list);
}
return list;
}
탐색 종료 시 list의 값 -> ["A", "B", "D", "H", "I", "E", "J", "K", "C", "F", "L", "M", "G", "N", "O"]- 중위 순회 (inorder traverse)
중위 순회는 루트를 가운데 두고 순회한다.
제일 왼쪽 끝에 있는 노드부터 순회하기 시작해서 루트를 기준으로 왼쪽에 있는 노드의 순회가 끝나면 루트를 거쳐 오른쪽에 있는 노드로 이동하여 마저 방문한다.
부모 노드가 서브 트리의 방문 장간에 방문되는 순회 방식이라고 할 수 있다.
중위 순회는 BST의 오름차순으로 값을 가져올 때 쓰인다.
/* 최소한의 기능만 구현되어 있습니다.
자식 노드가 없는 경우는 node == null이라고 가정합니다.
이미 이진 트리는 구현되어 있다고 가정합니다. */
class Node {
String data;
Node left;
Node right;
public Node getLeft() {
return left;
}
public String getData() {
return data;
}
public Node getRight() {
return right;
}
}
public ArrayList<String> inOrder(Node node, ArrayList<String> list) {
if (node != null) {
list = inOrder(node.getLeft(), list);
list.add(node.getData());
list = inOrder(node.getRight(), list);
}
return list;
}
탐색 종료 시 list의 값 -> ["H", "D", "I", "B", "E", "J", "K", "A", "L", "F", "M", "C", "N", "G", "O"]- 후위 순회 (postorder traverse)
후위 순회는 루트를 가장 마지막에 순회한다.
제일 왼쪽 끝에있는 노드부터 순회하기 시작해서 루트를 거치지 않고 오른쪽으로 이동해 순회한 뒤, 제일 마지막에 루트를 방문한다.
후위 순회는 트리를 삭제할 때 사용한다. (자식 노드가 먼저 삭제되어야 상위 노드를 삭제할 수 있기 때문에)
/* 최소한의 기능만 구현되어 있습니다.
자식 노드가 없는 경우는 node == null이라고 가정합니다.
이미 이진 트리는 구현되어 있다고 가정합니다. */
class Node {
String data;
Node left;
Node right;
public Node getLeft() {
return left;
}
public String getData() {
return data;
}
public Node getRight() {
return right;
}
}
public ArrayList<String> postOrder(Node node, ArrayList<String> list) {
if (node != null) {
list = postOrder(node.getLeft(), list);
list = postOrder(node.getRight(), list);
list.add(node.getData());
}
return list;
}
탐색 종료 시 list의 값 -> ["H", "I", "D", "J", "K", "E", "B", "L", "M", "F", "N", "O", "G", "C", "A"]
