비선형 자료구조 정리 (트리)

트리(Tree) 란?

비선형 구조는 선형구조와는 다르게 데이터가 계층적(혹은 망)으로 구성되어있습니다. 선형구조와 비선형구조의 차이점은 구성형태뿐만 아니라 용도에서도 차이점이 있습니다. 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져있습니다. 그렇다면 트리는 무엇을 표현하기 위한 자료구조일까요?

 

[그림 1] 컴퓨터의 디렉토리 구조

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

 

관련 용어

[그림 2] 트리 구조 예제

• 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)

[그림 3] full tree와 complete tree 예제

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

구현에 앞서

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

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

[그림 4] 이진 트리 구현

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

 

구현

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,2,3는 1,2,3을 데이터로 갖는 노드이며, bt4는 "song"을 갖는 노드입니다.

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

 

                            bt1

                     bt2          bt3

                bt4

 

결과값을 대략적으로 시각화 한다면 위 그림과 똑같아집니다.

 

트리의 탐색

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