[알고리즘] 2.3.자료구조 : 트리(Tree) 이해하기와 구현

  개요

앞서 보인 큐(Queue), 스택(Stack) 등은 자료구조에서 선형 구조라 한다. 선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미합니다. 이번에 배울 트리는 비선형 구조입니다. 비선형 구조는 선형구조와는 다르게 데이터가 계층적(혹은 망)으로 구성되어있습니다. 선형구조와 비선형구조의 차이점은 구성형태뿐만 아니라 용도에서도 차이점이 들어나는데요, 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다. 그렇다면 트리는 무엇을 표현하기 위한 자료구조일까요? 

컴퓨터의 directory 구조가 트리의 대표적인 예가 될 수 있습니다. 어떠한 프로그램, 사진, 영상 등을 찾을 때 우리는 폴더에서 폴더로 들어가면서 찾곤 합니다. 이렇게 계층적인 구조를 갖는 것이 트리라 할 수 있습니다. 또 다른 예로는 조직도, 족보 등이 있습니다. 

  관련 용어

 

• Root Node : 트리 구조에서 최상위에 존재하는 A와 같은 노드
• Node : 트리의 구성요소에 해당하는 A,B,C,D,E,F,G,H,I,J와 같은 요소
• Edge : 노드와 노드를 연결하는 연결설
• Terminal Node(Leaf Node) : 밑으로 또 다른 노드가 연결되어 있지 않은 H,I,J,F,G와 같은 노드
• Sub-Tree : 큰 트리(전체)에 속하는 작은 트리
• Level : 트리에서 각 층별로 숫자를 매김
• Height : 트리의 최고 레벨 (3)

• 이진트리 : "이진 트리가 되려면, 루트 노드를 중심으로 둘로 나뉘는 두 개의서브트리도 이진 트리이어야 하고, 그 서브 트리의 모든 서브 트리도 이진트리이어야 한다." 
  
• 포화 이진 트리(Full Binary Tree) : 모든 레벨이 꽉 찬 이진 트리
• 완전 이진 트리(Complete Binart Tree) : 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 틈 없이 노드가 채워진 이진 트리

  구현에 앞서

트리 또한 배열과 연결리스트 모두 사용하여 구현이 가능합니다. 하지만 배열을 이용한 트리 구현은 힙(heap)이라는 자료구조와 관련이 있어 배열을 이용한 트리 구현은 다음에 정리하도록 하겠습니다.

트리를 구현한다는 것은 너무나도 포괄적인 표현입니다. 트리의 모양은 자기가 만들고 싶은대로 만들 수가 있어, 모든 트리를 표현할 수 있는 코드를 구현하기는 어렵습니다. 따라서 트리의 대표라 할 수 있는 이진트리(자식이 2개 이하)를 구현하도록 하겠습니다. 

연결 리스트 기반의 트리 구현 방식은 하나의 노드에 왼쪽 자식, 오른쪽 자식의 정보를 담는 변수와 자신이 가지는 데이터만 있으면 됩니다. 위 그림을 보면 한 노드에 세개의 칸이 있습니다. 가장 위에 있는 칸이 자신이 갖는 데이터이고, 그 아래의 두개의 칸은 자식의 정보를 담는 칸입니다. 그러면 일단 코드를 보고 자세히 살펴보도록 하겠습니다.

  구현

public class TreeNode {

private TreeNode left;

private TreeNode right;

private Object data;

public TreeNode(Object item){

left = null;

right = null;

data = item;

}

 //자신과 왼쪽 자식 노드(sub)와 연결해주는 method

public void makeLeftSubTree(TreeNode sub){

   if(this.left != null) this.left = null;

this.left = sub;

}

 //자신과 오른쪽 자식 노드(sub)와 연결해주는 method

public void makeRightSubTree(TreeNode sub){

   if(this.right != null) this.right = null;

this.right = sub;

}

 //자신의 data를 반환하는 함수

public Object getData(){

  return this.data;

}

 //자신의 왼쪽 자식노드를 반환하는 함수

public TreeNode getLeftSubTree(){

  return this.left;

}

 //자신의 오른쪽 자식노드를 반환하는 함수

public TreeNode getRightSubTree(){

  return this.right;

}

}

Tree노드의 프로퍼티로는 자식을 담는 변수 2개(왼쪽, 오른쪽)와 자신의 데이터(data)가 있습니다. 

메쏘드로는 public void makeLeftSubTree(TreeNode sub) 매개변수인 sub노드를 자신의 왼쪽 자식으로 연결시켜주는 메쏘드입니다. 만약 왼쪽 자식이 연결 이전에 있었으면 null로 만든 후에 연결시켜줍니다. 오른쪽 자식을 연결시켜주는 메쏘드도 같은 방식으로 구현됩니다.

나머지는 get함수로 Tree노드의 프로퍼티를 가져오는 메쏘드입니다. (getData(), getLeftSubTree(), getRightSubTree())

public class main {

public static void main(String[] args) {

TreeNode bt1 = new TreeNode(1);

TreeNode bt2 = new TreeNode(2);

TreeNode bt3 = new TreeNode(3);

TreeNode bt4 = new TreeNode("song");

bt1.makeLeftSubTree(bt2);

bt1.makeRightSubTree(bt3);

bt2.makeLeftSubTree(bt4);

//bt1의 왼쪽 자식노드의 데이터 출력

System.out.println(bt1.getLeftSubTree().getData());

//bt1의 오른쪽 자식노드의 데이터 출력

System.out.println(bt1.getRightSubTree().getData());

}

}

트리 노드를 4개를 생성합니다. bt1은 1을 데이터로 갖는 노드입니다. bt2는 2를, bt3은 3을, bt4는 "song"을 갖는 노드입니다. 

4개의 노드를 트리 형태로 연결 시켜줄 것인데, 루트노드는 bt1으로 하였습니다. bt1의 왼쪽 자식은 bt2로, 오른쪽 자식은 bt3으로 연결시켜주었고, bt4는 bt2의 왼쪽자식으로 연결시켜주었습니다. 

bt1

bt2        bt3

bt4

이런 식으로 연결시켜주었습니다. 루트노드와 왼쪽 자식 오른쪽 자식은 자신의 마음대로 정할 수 있으며, 노드가 갖는 데이터도 마음대로 정할 수 있습니다. 

  트리의 탐색

지금까지 트리를 구현하였는데, 구현된 트리를 탐색하는 방법은 다음 글에 공부하도록 하겠습니다. 트리는 스택이나 큐와 다르게 비선형구조로 탐색하는 방법이 여러가지가 있습니다. 위에 구현된 간단한 트리만 보더라도 b4-b2-b1-b3 순으로 탐색할 수 있고, b1-b2-b4-b3 순으로 탐색 할 수도 있습니다. 이렇게 트리에 있는 모든 노드들을 탐색하는 것을 트리 순회(Traversal)이라 합니다.