[자료구조, Java] 트리(Tree) 개념 정리 및 구현

소개

Tree는 비선형 자료구조 중 하나입니다.

비선형이라는 것은 말 그대로 일직선으로 나타내지 못하는 방식이며, 그중 트리는 계층적 구조를 띄고 있습니다.

계층적 구조라 함은, 일반적으로 조직도를 나타내는 경우 자주 사용되죠. 트리도 그와 비슷합니다.

 

자료구조를 학습할 때, 사람들이 가장 많이 포기하시는 경우가 선형 자료구조를 어렵게 어렵게 배우고, 비선형 자료구조로 넘어갈 때라는 것 아시나요? (윤성우의 열혈 자료구조 내용)

일반적으로 저희는 나란히 자료가 저장되고, 삭제되는 메커니즘에 익숙합니다. 그런데 갑자기 익숙하지 않게 계층적으로 자료를 저장하고 삭제하려니 난이도가 급증했음을 느끼게 되고, 곧 포기하게 되는 거죠.

 

부족하지만, 이 게시글이 조금이라도 도움이 되시길 바랍니다...

 

구조

아까 말씀드렸다시피 계층적인 구조를 띄고 있습니다.

트리를 아예 처음 접하신 경우, 이런 생각이 드실 거예요.

 

"어떻게 값을 저런 형태로 저장하지?"

 

라는 의문이 드실 텐데, 보통 다음과 같이 처리합니다.

1. 데이터와 연결 상태를 저장할 클래스 공간(=노드) 생성

2. 각각의 노드들에 값 저장

3. 노드 간 연결 상태 정의

 

해당 순서를 더 상세하게 설명하겠습니다.

1. 데이터를 저장할 클래스 공간(=노드) 생성

 Node라는 클래스를 만들고, 저장할 값 변수, 왼쪽 연결 노드, 오른쪽 연결 노드에 대한 정보를 저장할 변수. 이렇게 총 3개를 필드로 정의합니다.

코드로 생성하자면, 다음과 같습니다.

 

2. 각각의 노드들에 값 저장

3개의 노드를 생성하고, 우선 leftNode와 rightNode에 대한 정보를 null로 초기화했습니다.

 

3. 노드 간 연결 상태 정의

Node1의 leftNode : Node2

Node1의 rightNode : Node3

을 다음과 같이 표현할 수 있습니다.

코드로 나타내면, 다음과 같습니다.

다음과 같은 연결 상태들을 정의하여, 처음 보여드렸던 사진과 같이 나타내게 됩니다.

용어

루트(root) : 트리 구조 중 최상위에 존재하는 노드 (1을 가리킴)

노드(node) : 트리에서 각각의 구성 요소

레벨(level) : 트리에서 각각의 층을 나타내는 단어(루트 노드 : 0)

형제 노드(sibling) : 같은 레벨의 노드

간선(edge) : 노드와 노드를 연결하는 선

부모 노드(parent node) : 한 노드를 기준으로 바로 상위에 존재하는 노드

자식 노드(child node) : 한 노드를 기준으로 바로 하위에 존재하는 노드

높이(heigh) : 트리 중 최고 레벨

 

이진트리

트리는 다양한 모양으로 존재할 수 있다. 예를 들자면 다음과 같다.

이 사진의 경우, 자식 노드를 4개를 갖는다고 표현할 수 있다.

 

다만, 일반적으로 학습을 위해서는 편의를 위해 왼쪽/오른쪽 각각 하나씩, 총 2개인 이진트리를 기준으로 학습하곤 한다.

따라서, 자식 노드가 최대 2개인 트리를 이진트리라고 한다.

 

순회 방법

순회 방법은 전위(pre-order), 중위(in-order), 후위(post-order) 순회가 있다.

함께 순서를 보기 전, 각각의 순회를 먼저 정의하자면,

전위 순회(pre-order) : 루트 노드를 먼저 순회한 이후, '왼쪽 하위 -> 오른쪽 하위' 순으로 순회하는 방법.

중위 순회(in-order) : 왼쪽 가장 하위 노드를 먼저 순회한 이후, '바로 상위 노드 -> 오른쪽 하위' 순으로 순회하는 방법.

후위 순회(pre-order) : 왼쪽 가장 하위 노드를 먼저 순회한 이후, '오른쪽 하위 노드 -> 바로 상위 노드' 순으로 순회하는 방법

이다.

탐색 순서를 함께 보면 좋을 것 같다. 트리 사진은 가장 상단에 올렸던 사진이다.

전위 순회 순서 : 1 - 2 - 4 - 5 - 3 - 6 - 7

중위 순회 순서 : 4 - 2 - 5 - 1 - 6 - 3 - 7

후위 순회 순서 : 4 - 5 - 2 - 6 - 7 - 3 - 1

 

한 번에 이해가 되지 않아도 좋으니, 설명과 순서를 번갈아 가며 익히는 게 좋을 것 같다.

 

기능

Node

- void addLeft(Node node)

 현재 노드의 좌측에 노드 연결 정보를 추가한다.

- void addRight(Node node)

 현재 노드의 우측에 노드 연결 정보를 추가한다.

- void deleteLeft()

 현재 노드의 좌측 노드 연결 정보를 삭제한다.

- void deleteRight()

 현재 노드의 좌측 노드 연결 정보를 삭제한다.

Tree

- Node addNode(Object data)

 노드를 새롭게 생성한다.(저장될 데이터는 data 변수 안에 존재하는 값)

- void preOrder(Node node)

 전위 순회 방법을 이용해 출력한다.

- void inOrder(Node node)

 중위 순회 방법을 이용해 출력한다.

- void postOrder(Node node)

 후위 순회 방법을 이용해 출력한다.

 

구현

- Tree 클래스(Node 클래스 포함)

package Tree;

public class Tree {
	int count;
	
	public Tree() {
		count = 0;
	}
	
	public class Node {
		Object data;
		Node left;
		Node right;
	
		// 생성 시 매개변수를 받아 초기화하는 방법으로만 선언 가능
		public Node(Object data) {
			this.data = data;
			left = null;
			right = null;
		}

		public void addLeft(Node node) {
			left = node;
			count++;
		}

		public void addRight(Node node) {
			right = node;
			count++;
		}

		public void deleteLeft() {
			left = null;
			count--;
		}

		public void deleteRight() {
			right = null;
			count--;
		}
	}
	
	public Node addNode(Object data) {
		Node n = new Node(data);
		return n;
	}
	
	public void preOrder(Node node) {
		if(node == null) {
			return;
		}
		
		System.out.print(node.data + " ");
		preOrder(node.left);
		preOrder(node.right);
	}

	public void inOrder(Node node) {
		if(node == null) {
			return;
		}
		
		inOrder(node.left);
		System.out.print(node.data + " ");
		inOrder(node.right);
	}

	public void postOrder(Node node) {
		if(node == null) {
			return;
		}
		
		postOrder(node.left);
		postOrder(node.right);
		System.out.print(node.data + " ");
	}
}

 

- Run 클래스(코드 실행 클래스)

import Tree.*;
import Tree.Tree.Node;

public class Run {
	public static void main(String[] args) {
		// 트리 생성
		Tree tree = new Tree();
		
		// 노드 생성
		Node node1 = tree.addNode(1);
		Node node2 = tree.addNode(2);
		Node node3 = tree.addNode(3);
		Node node4 = tree.addNode(4);
		Node node5 = tree.addNode(5);
		Node node6 = tree.addNode(6);
		Node node7 = tree.addNode(7);
		
		// 트리 연결관계 생성
		/*  트리 모양       
		 *        1
		 *     2     3
		 *   4  5  6   7
		 */
		node1.addLeft(node2);
		node1.addRight(node3);
		node2.addLeft(node4);
		node2.addRight(node5);
		node3.addLeft(node6);
		node3.addRight(node7);
		
		// 순회
		tree.preOrder(node1);
		System.out.println();
		tree.inOrder(node1);
		System.out.println();
		tree.postOrder(node1);
		System.out.println();
		
		// 삭제
		node2.deleteLeft();
		node3.deleteRight();
		/* 삭제 이후 트리 모양
		 *        1
		 *     2     3
		 *      5  6   
		 */
		
		// 순회
		System.out.println();
		tree.preOrder(node1);
		System.out.println();
		tree.inOrder(node1);
		System.out.println();
		tree.postOrder(node1);
		System.out.println();
	}
}

 

감사합니다.

설명이 틀리거나, 부족하거나, 질문 있으시면 댓글 남겨주세요!