티스토리 뷰
이번 포스팅에서는 비선형 자료구조인 트리중 이진트리에 대해 다뤄보겠다.
우선 비선형 자료구조란 무엇인가 정의를 살펴보면,
비순차적인 성질을 지닌 자료들을 표현하는데 적합한 구조.
라고 명시 되어있다.
이런 비선형 자료구조에는 그래프와 트리로 나뉘고 이번에 다룰 이진 트리는 이런 트리의 일종이다.
트리의 정의는 하단의 링크를 참조하도록 하겠다.
https://terms.naver.com/entry.naver?docId=2270428&cid=51173&categoryId=51173
트리
트리(tree) 구조는 나무를 뒤집은 모습으로 계층 구조를 표현하기에 적합하다. 계층 구조의 대표적인 예가 회사 또는 대학의 조직도인데 다음은 J 대학의 조직도 일부를 나타낸 것이다. 다음은 [
terms.naver.com
요약하자면 계층구조를 표현하기에 적합한 자료구조로
최상단의 노드를 루트라고 하고 최하단의 노드를 리프라고 표현한다.
루트를 제외한 모든 노드는 유일한 부모노드를 갖고 트리에서 임의의 노드를 선택하면 해당 노드를 기준으로
노드 하위의 모든 노드는 또 하나의 서브 트리가 된다.
위 그림을 예로 들어 좀 더 부연 설명하자면 루트노드인 A를 제외한 모든 노드는 부모노드를 갖고
B의 자식 노드는 D,E,F 이고 D,E,F의 부모노드는 B인것이다.
이런 트리는 그 형태에 따라 여러가지로 나눌수 있는데 이번에 다뤄볼 이진트리는
한 노드당 자식노드가 2개까지 밖에 없는 형태의 구조를 말한다.
즉 모든 노드들의 자식노드가 2개 이하이면 이진트리이다.
또 이진트리중에서도 리프노드를 제외한 모든 노드의 자식노드가 2개인 이진트리를 완전 이진 트리라고 하며,
모든 노드가 채워진 이진트리를 포화 이진트리라고 한다.
이러한 이진트리는 순회 할 수 있는데
순회란 각 노드를 한번씩만 방문하여 모든 모드를 방문하는것을 말한다.
그리고 순회 방법에는 전위 순회, 중위순회, 후위순회가 있다.
먼저 전위 순회부터 살펴보자면,
루트 - 왼쪽 서브트리 - 오른쪽 서브트리의 순서로 이루어진다.
간단한 그림을 통해 자세히 살펴보겠다.
A 부터 I까지의 과정을 설명하자면,
먼저 루트 노드인 A에서 순회를 시작하여 왼쪽 서브 트리인 B로 이동하고 그 다음 왼쪽 서브트리인 D로 이동하고,
H로 이동후 오른쪽 서브트리인 I로 이동하게된다.
즉 루트 - 왼쪽서브트리 - 오른쪽 서브트리의 순서로 순회하는것이다.
다음으론 중위 순회를 살펴보도록 하겠다.
중위순회는
왼쪽서브트리 - 루트 - 오른쪽 서브트리의 순서로 진행된다.
왼쪽서브트리 - 루트 - 오른쪽 서브트리로 진행되므로
먼저 루트의 왼쪽 서브트리인 B를 기준으로 한 서브트리를 먼저 방문한다.
현재 서브트리의 루트는 B이므로 B의 왼쪽 서브트리인 D를 기준으로하는 서브트리를 방문하고
또 그에 따른 왼쪽 서브트리이자 리프노드인 H를 최초 방문하게 된다.
그리고 순서에 따라 서브트리의 루트인 D 방문후 오른쪽 서브트리인 I를 방문하게 되면
B를 기준으로 한 서브트리의 왼쪽 서브트리 방문이 끝났으므로 루트인 B를 방문,
그리고 오른쪽 서브트리로 진행하는 것이다.
마지막으로 후위 순회는
왼쪽 서브트리 - 오른쪽 서브트리 - 루트의 순서로 순회한다.
왼쪽 서브트리 - 오른쪽 서브트리 - 루트의 순서로 방문하므로
왼쪽서브트리로 쭉 타고 내려가 리프노드에 위치한 H 부터 방문을 한뒤, 오른쪽 서브트리인 I 방문,
그리고 루트인 D를 방문한다. 그리고 B를 기준으로 한 서브트리의 왼쪽 트리가 모두 방문이 완료됐으므로
오른쪽 서브트리의 왼쪽 서브트리인 J를 방문하게 되는것이다.
이런 일련의 과정을 통해 전체 트리의 루트인 A가 가장 마지막에 방문하면서 순회하게 된다.
그렇다면 이제 이를 코드로 구현해보도록 하겠다.
가장 일반적으로 사용하는 방식인 재귀를 사용한 구현을 할것이다.
우선 각 노드를 표현하기 위한 클래스를 하나 선언해주도록 하겠다.
현재 노드에 대해 저장할 멤버변수, 그리고 이진 트리이므로 왼쪽 자식노드, 오른쪽 자식 노드에 대해
멤버변수로 선언해주고
생성자로 현재 노드의 값을 받도록 한다.
class Node{
char data;
Node left;
Node right;
Node(char data){
this.data = data;
}
}
그리고 트리에 대한 클래스를 생성하도록 하겠다.
이진트리의 기준이되는 루트를 멤버변수로 선언해준다.
이때 자료형은 이전에 선언한 노드클래스를 사용한다.
public class TreeTraversal {
public Node root;
}
이제 각 노드에 대한 데이터를 인자로 받아 트리를 생성할 메소드,
그리고 그 안에서 현재 입력받은 노드의 부모자식 관계를 따져 현재 노드의 위치를 찾아줄 메소드를 만들도록 하겠다.
public void init(char data, char leftData, char rightData){
}
private void searchNode(Node node, char data, char leftData, char rightData){
}
init 메소드에서는 현재 노드의 데이터와 그리고 자식노드들의 데이터를 인자로 받고
처음 받는 데이터를 루트로 지정후 차후에 받는 데이터들에 대해 searchNode 메소드를 통해
각 노드의 위치를 찾아 저장하도록 한다.
public void init(char data, char leftData, char rightData) {
if(this.root == null) {
root = new Node(data);
if(leftData != 0) {
root.left = new Node(leftData);
}
if(rightData != 0) {
root.right = new Node(rightData);
}
}else {
searchNode(root,data,leftData,rightData);
}
}
searchNode 메소드는 현재 노드가 null이라면 리턴
null 이 아닌경우 현재 노드의 데이터와 인자로 받는 데이터가 일치하다면
현재 위치로 노드위치 지정
일치하지 않다면 재귀호출을 통해 현재 입력받은 데이터의 위치를 찾도록 한다.
private void searchNode(Node node,char data, char leftData, char rightData) {
if(node == null) return;
if(node.data == data) {
if(leftData != 0) {
node.left = new Node(leftData);
}
if(rightData != 0) {
node.right = new Node(rightData);
}
}else {
searchNode(node.left,data,leftData,rightData);
searchNode(node.right,data,leftData,rightData);
}
}
이제 전위 , 중위 , 후위 순회 메소드를 각각 만들어준다.
각 노드를 방문할때 마다 순서에 맞게 노드의 데이터를 출력하도록 했다.
전위순회는 루트 - 왼쪽트리 - 오른쪽트리 순으로 순회하므로
public void preOrder(Node node) {
if(node != null) {
System.out.print(node.data);
System.out.print(' ');
preOrder(node.left);
preOrder(node.right);
}
}
다음과 같이 재귀를 통해 간단히 구현할수 있다.
중위 순회는 왼쪽트리 - 루트 - 오른쪽트리 순으로 순회하므로
역시 재귀로 간단히 구현이 가능하다.
public void inOrder(Node node) {
if(node != null) {
inOrder(node.left);
System.out.print(node.data);
System.out.print(' ');
inOrder(node.right);
}
}
마지막 후위 순회도 왼쪽트리 - 오른쪽트리 - 루트 순으로 순회하므로
재귀로 구현이 가능하다.
public void postOrder(Node node) {
if(node != null) {
postOrder(node.left);
postOrder(node.right);
System.out.print(node.data);
System.out.print(' ');
}
}
아래는 코드의 전문이다.
package test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class TreeTraversal {
public Node root;
public void init(char data, char leftData, char rightData) {
if(this.root == null) {
root = new Node(data);
if(leftData != 0) {
root.left = new Node(leftData);
}
if(rightData != 0) {
root.right = new Node(rightData);
}
}else {
searchNode(root,data,leftData,rightData);
}
}
private void searchNode(Node node,char data, char leftData, char rightData) {
if(node == null) return;
if(node.data == data) {
if(leftData != 0) {
node.left = new Node(leftData);
}
if(rightData != 0) {
node.right = new Node(rightData);
}
}else {
searchNode(node.left,data,leftData,rightData);
searchNode(node.right,data,leftData,rightData);
}
}
public void preOrder(Node node) {
if(node != null) {
System.out.print(node.data);
System.out.print(' ');
preOrder(node.left);
preOrder(node.right);
}
}
public void inOrder(Node node) {
if(node != null) {
inOrder(node.left);
System.out.print(node.data);
System.out.print(' ');
inOrder(node.right);
}
}
public void postOrder(Node node) {
if(node != null) {
postOrder(node.left);
postOrder(node.right);
System.out.print(node.data);
System.out.print(' ');
}
}
public static void main(String[] args) throws IOException{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
TreeTraversal tree = new TreeTraversal();
char[] data;
for(int i = 0; i < n; i++) {
data = in.readLine().toCharArray();
tree.init(data[0],data[1],data[2]);
}
in.close();
System.out.print("전위 순회 : ");
tree.preOrder(tree.root);
System.out.println();
System.out.print("중위 순회 : ");
tree.inOrder(tree.root);
System.out.println();
System.out.print("후위 순회 : ");
tree.postOrder(tree.root);
}
}
class Node{
char data;
Node left;
Node right;
Node(char data){
this.data = data;
}
}
이제 앞서 다루었던 이진트리를 예시데이터로 삽입해보겠다.
7
ABC
BDE
DHI
EJK
CFG
FLM
GNO
앞서 설명한 순서와 동일하게 출력되는것을 확인할수 있다.
'알고리즘 > 구현' 카테고리의 다른 글
| [자료구조] 힙(heap) 의 구현 (JAVA) + 우선 순위 큐 (0) | 2023.09.18 |
|---|---|
| 유클리드 호제법(JAVA) (0) | 2023.09.17 |
| [자료구조] 큐(Queue)의 구현(JAVA) (0) | 2023.09.13 |
| [자료구조] 스택(Stack) 구현 (JAVA) (0) | 2023.09.12 |
| BFS(너비 우선 탐색) 구현 (JAVA) (0) | 2023.09.04 |