알고리즘 기본기 다지기6.기초 데이터구조 (트리)

트리

트리는 대표적으로 우리가 사용하는 컴퓨터의 폴더, 회사나 어느 조직의 구성도 모양의 데이터 구조이다. 맨 위의 대표 개체로부터 아래로 갈수록 가지가 많아지는 계층 구조를 트리라고 부른다. 계츠 구조가 한줄기로 시작하여 모양이 넓어지는 일반적인 트리의 형태와 비슷하다.

트리는 계층적으로 저장된 데이터 원소들을 모델링한다.

트리 용어

• 노드(node) : 데이터 원소
• 간선(edge) : 노드 사이를 연결하는 선
• 루트(root) : 트리의 맨 위 부모가 없는 노드, 최상위 노드
• 내부노드(internal node) : 중간노드라고 불린다. 한개의 자식을 가진 노드
• 외부노드(external node) : 자식이 없는 노드
• 부트리(subtree) : 노드와 그 노드의 자손들로 구성된 트리, 트리 안의 트리
• 경로(path) : 특정 조상으로부터 특정 자손을 따라 이어진 노드의 길이, 이어진 간선의 갯수(=경로길이)
• 깊이(depth) : 특정 노드로부터 외부노드에 이르는 가장 긴 경로의 길이
• 높이(height) : 루트로부터 외부노드에 이르는 가장 긴 경로의 길이 
• 순서트리(ordered tree) : 각 노드의 자식들에 대해 선형 순서가 정의되어있는 트리
• 무순트리(unordered tree) : 순서가 정의되지 않은 트리

트리 깊이와 높이

두 값을 구하는데에는 재귀적으로 정의할 수 있다.

최악의 경우, 모든 노드를 탐방하는 O(n) 시간을 수행하게 된다.

순회(Traversla)

트리의 매우 중요한 작업으로 순회가 있다. 순회란 트리의 노드들을 체계적인 방식으로 방문하는 것이다.

트리 순회에는 선위순회(preordered traversal), 후위순회(postorder traversal) 방식이 있다.

선위순회에서는 노드가 그의 자손들 보다 먼저 방문된다.

후위순회에서는 노드가 자손들보다 나중에 방문된다.

순회방식은 모든 노드를 탐방하는 것이기 때문에 O(n) 시간을 수행하게 된다.

이진트리(Binary Tree)

이진트리는 트리의 확장 자료구조 이다. 이진 트리는 순서 트리를 기반으로 생성된다.

트리는 자식노드를 최대 2개 갖을 수 있다.

각각 왼쪽/오른쪽 자식을 가질 수 있다.

깊이(depth)

이진트리에서 깊이와 높이는 트리에서의 깊이와 높이와 동일하다.

이진트리에서 깊이(depth)는 만약  노드 v가 루트일 경우, 깊이는 0 이라고 한다.

• 노드 v의 깊이 = v의 부모의 깊이 + 1

높이(height)

만약 노드 v가 외부노드(자식 노드가 X)이면, v 의 높이는 0이다.

• 노드 v의 높이 = 왼쪽과 오른쪽 자식 중 최대 높이 + 1

이진트리 순회

이진트리는 트리의 선위순회, 후휘순회를 진행한다. 또한 이진트리에서는 중위순회(inordder traversal)가 존재한다.

순회는 모든 노드를 탐바하기 때문에 O(n)시간을 수행한다.

완전이진트리(Complete Binary Tree)

이진트리에서 노드의 공간 낭비 없이 모든 공간을 사용하는 트리 구조이다.

 

문제풀이

백준 1991. 트리 순회(이진트리)

package tree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import org.junit.jupiter.api.Test;

/*
 * 이진 트리를 입력받아 전위 순회(preorder traversal)
 * , 중위 순회(inorder traversal)
 * , 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.
 * */
public class Backjun1991 {
	
	@Test
	public void test() {
		Tree tree = new Tree();
		tree.insertNode("A B C");
		tree.insertNode("B D .");
		tree.insertNode("C E F");
		tree.insertNode("E . .");
		tree.insertNode("F . G");
		tree.insertNode("D . .");
		tree.insertNode("G . .");
		
		tree.preOrder(tree.root);
		System.out.println();
		tree.inOrder(tree.root);
		System.out.println();
		tree.postOrder(tree.root);
		System.out.println();
	}

	@Test
	public void test2() {
		Tree tree = new Tree();
		tree.insertNode("A B C");
		tree.insertNode("B D E");
		tree.insertNode("C F G");
		tree.insertNode("D H I");
		tree.insertNode("E J K");
		tree.insertNode("F L M");
		tree.insertNode("G N O");
		tree.insertNode("H P Q");
		tree.insertNode("I R S");
		tree.insertNode("J T U");
		tree.insertNode("K V W");
		tree.insertNode("L X Y");
		tree.insertNode("M . .");
		tree.insertNode("N . .");
		tree.insertNode("O . .");
		tree.insertNode("P . .");
		tree.insertNode("Q . .");
		tree.insertNode("R . .");
		tree.insertNode("S . .");
		tree.insertNode("T Z .");
		tree.insertNode("U . .");
		tree.insertNode("V . .");
		tree.insertNode("R . .");
		tree.insertNode("X . .");
		tree.insertNode("Y . .");
		tree.insertNode("Z . .");
		
		tree.preOrder(tree.root);
		System.out.println();
		tree.inOrder(tree.root);
		System.out.println();
		tree.postOrder(tree.root);
		System.out.println();
	}
	@Test
	public void test3 () {
		Tree tree = new Tree();
		tree.insertNode("A B C");
		
		tree.preOrder(tree.root);
		System.out.println();
		tree.inOrder(tree.root);
		System.out.println();
		tree.postOrder(tree.root);
		System.out.println();
	}

	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String str = br.readLine();
			//1. 이진트리의 노드의 개수
			int n = Integer.valueOf(str);
			//2.n개의 줄에 걸쳐 노드와 왼쪽자식노드, 오른쪽 자식 노드 생성
			Tree tree = new Tree();
			for(int i=0; i< n ;i++) {
				tree.insertNode(br.readLine());
			}
			
			//3. 전위순회
			tree.preOrder(tree.root);
			System.out.println();
			
			//4. 중위순회
			tree.inOrder(tree.root);
			System.out.println();
			
			//5. 후위순회
			tree.postOrder(tree.root);
			
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

class Node {
	String element;
	Node left;
	Node right;
	
	public Node(String e){
		element = e;
	}
}
class Tree {
	Node root;
	public void insertNode(String line) {
		String[] arr = line.split(" ");

		if(root == null) {
			root = new Node(arr[0]);
			root.left = getElemenet(arr[1])==null?null:new Node(getElemenet(arr[1]));
			root.right = getElemenet(arr[2])==null?null:new Node(getElemenet(arr[2]));
		}
		else {
			Search(root, arr[0], arr[1], arr[2]);
		}
	}
	public void Search(Node node, String element, String left, String right) {
		if(node == null) return;
		
		if(node.element.equals(element)) {
			node.left = getElemenet(left)==null?null:new Node(getElemenet(left));
			node.right = getElemenet(right)==null?null:new Node(getElemenet(right));
		}
		else {
			Search(node.left, element, left, right);
			Search(node.right, element, left, right);
		}
	}
	public String getElemenet(String e) {
		if(e.equals(".")) {return null;}
		else {
			return e;
		}
	}
	public void preOrder(Node node) {
		System.out.print(node.element);
		if(node.left != null) preOrder(node.left);
		if(node.right != null) preOrder(node.right);
	}
	public void inOrder(Node node) {
		if(node.left != null) inOrder(node.left);
		System.out.print(node.element);
		if(node.right != null) inOrder(node.right);
	}
	public void postOrder(Node node) {
		if(node.left != null) postOrder(node.left);
		if(node.right != null) postOrder(node.right);
		System.out.print(node.element);
	}
}

 

 

참조

알고리즘 국형준
https://ko.wikipedia.org/wiki/%EB%8D%B1_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)