[백준] 1991 트리 구조 -Java / Python

 

 

 

비선형 자료구조인 트리 구조를 알아야 풀 수 있는 문제다.

 

트리 구조는 노드를 사용해서 데이터를 저장하고, 노드는 저장된 값, 하위에 있는 여러 가지 노드들로 구성된다.

여기서 하위에 있는 노드의 개수가 2개 뿐인 노드를 이진트리라고 한다.

 

트리의 순회 방법에는 세 가지가 있다.

 

1. 전위 순회

루트 노드를 순회한 다음 왼쪽 하위를 거쳐 오른쪽 하위로 순회하는 방법.

 

2. 중위 순회

왼쪽 하위 노드부터 시작해 루트 노드까지 순회하고 오른쪽 하위 노드부터 다시 순회하는 방법.

 

3. 후위 순회

왼쪽부터 시작해 가장 하위 계층에 있는 노드를 순회한 다음 오른쪽을 거쳐 루트 노드로 순회하는 방법

 

트리에 대한 개념은 어렵지 않지만, 이 개념만을 가지고 코드로 구현하려면 막막하다.. 

 

Java

 

트리 구조를 구현할 때 자바의 객체지향 개념이 유용하게 사용된다. 

재귀를 사용해서 탐색하는 부분에 집중하자.

 

코드를 한줄 한줄 이해하면서 읽어보자.

 

어떻게 이런 방법을 생각해냈는지.. 참 신기하다. 꾸준히 공부해서 숙지해야겠다.

 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());

		Tree t = new Tree();

		for(int i=0; i<N; i++){
			String[] arr = br.readLine().split(" ");
			t.create(arr[0].charAt(0), arr[1].charAt(0), arr[2].charAt(0));	
		}

		t.preorder(t.root);
		System.out.println();

		t.inorder(t.root);
		System.out.println();

		t.postorder(t.root);


		
	}
	
	static class Node{ 
		char value = ' ';
		Node left;
		Node right;

		Node(char value){
			this.value = value;
		}
	} // 노드 객체를 만들기. 이진 트리이므로 노드는 값과 왼쪽과 오른쪽 노드로 구성됨.

	static class Tree{
		Node root;

		 void create(char value, char leftvalue, char rightvalue){
			if(root == null){ // 입력받을 때 루트 노드가 비어있으면 (제일 처음 입력받을 때) 노드를 생성한다.
				root = new Node(value);

				if(leftvalue != '.'){ // . 을 입력받으면 노드를 생성하지 않는다
					root.left = new Node(leftvalue);
				}

				if(rightvalue != '.'){// .을 입력받으면 노드를 생성하지 않는다
					root.right = new Node(rightvalue);
				}
			}else{ // 처음 상태가 아니면 어느 쪽에 노드를 생성할 지 찾아야 함.
				searchNode(root, value, leftvalue, rightvalue);
			}
		}

		void searchNode(Node root, char value, char leftvalue, char rightvalue){ // 초기 상태가 아닌 노드를 결정할 때 사용.
			if(root == null){ // 루트 노드를 입력받지 않으면 노드를 만들지 않음
				return;
			}else if(root.value == value){// 탐색에 성공했을 때 노드를 생성함

				if(leftvalue != '.'){
					root.left = new Node(leftvalue);
				}

				if(rightvalue != '.'){
					root.right = new Node(rightvalue);
				}
			}else{ // 탐색에 실패했고, 탐색할 노드가 남아있으면 계속해서 탐색을 진행함.
				searchNode(root.left, value, leftvalue, rightvalue);
				searchNode(root.right, value, leftvalue, rightvalue);
			}
		}

		void preorder(Node root){ // 전위 순회
			System.out.print(root.value); 
			if(root.left != null){
				preorder(root.left);
			}

			if(root.right != null){ 
				preorder(root.right);
			}
		}

		void inorder(Node root){ // 중위 순회
			if(root.left != null){
				inorder(root.left);
			}

			System.out.print(root.value);

			if(root.right != null){
				inorder(root.right);
			}

		}

		void postorder(Node root){ // 후위 순회
			if(root.left != null){
				postorder(root.left);
			}

			if(root.right != null){
				postorder(root.right);
			}

			System.out.print(root.value);

		}
	}

	
}

 

 

Python

 

파이썬에서도 클래스를 사용해서 동일하게 구현할 수 있긴 하지만, 딕셔너리를 사용하면 훨씬 더 간단하게 해결할 수 있다.

 

{A : [B , C]} 형식으로 구성되므로 이진 트리를 구성하기에 충분하다. 

 

딕셔너리 내부에 또 딕셔너리가 있고 그 딕셔너리 안에 또 딕셔너리가 있고... 재귀적으로 구성되며 결국 트리를 구성하기 때문에 세 가지 순회 모두 구현할 수 있다.

 

자바로 구현한 코드와 비교했을 때 방법은 좀 다르지만, 계층 구조를 만들어낸다는 결과는 같다. 

딕셔너리를 이렇게도 활용할수 있구나.. 싶다..

 

 

import sys

N = int(input())
tree = {}

for i in range(N):
  root, left, right = map(str, input().split(" "))
  tree[root] = left, right
  
def preorder(root):
  if root != '.':
    print(root, end='')
    preorder(tree[root][0])
    preorder(tree[root][1])

def inorder(root):
  if root != '.':
    inorder(tree[root][0])
    print(root, end='')
    inorder(tree[root][1])

def postorder(root):
  if root != '.':
    postorder(tree[root][0])
    postorder(tree[root][1])
    print(root, end='')


preorder('A')
print()
inorder('A')
print()
postorder('A')