[Python/Java] 백준 1991번 - 트리 순회

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

 

 

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 트리
 - 재귀

 

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

 

---

아주 단순한 이진 트리의 순회 문제 였다.

 

하지만 난 트리를 구현할 줄 몰랐다.

 

2023.04.08 - [Language/Java] - [Java] 트리 구현하기 (이진트리, 전위순회, 중위순회, 후위순회)

[Java] 트리 구현하기 (이진트리, 전위순회, 중위순회, 후위순회)

 

2023.04.11 - [Language/Python] - [Python] 트리 구현 하기

 

위를 참고하여 트리를 구현하면 된다.

 

참고로 Java의 코드는 조금 다른데

 

재귀를 통해 자기 자기 자신의 노드를 찾을때 까지 재귀하는 부분이 추가되어 있다.

 

(Java 코드)

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

public class Main {
	
	public static class Node {
		char data;
		Node leftNode;
		Node rightNode;
		
		public Node(char data) {
			this.data = data;
			this.leftNode = null;
			this.rightNode = null;
		}
		
		public void setLeftNode(Node node) {
			this.leftNode = node;
		}
		
		public void setRightNode(Node node) {
			this.rightNode = node;
		}
	}
	
	//전위 순회
	public static void preOrder(Node node) {
		if(node == null) {
			return;
		}
		System.out.print(node.data);
		preOrder(node.leftNode);
		preOrder(node.rightNode);
	}
	
	//중위 순회
	public static void inOrder(Node node) {
		if(node == null) {
			return;
		}
		inOrder(node.leftNode);
		System.out.print(node.data);
		inOrder(node.rightNode);
	}
	
	//후위 순회
	public static void postOrder(Node node) {
		if(node == null) {
			return;
		}
		postOrder(node.leftNode);
		postOrder(node.rightNode);
		System.out.print(node.data);
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		
		Node head = new Node('A');
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			char data = st.nextToken().charAt(0);
			char left = st.nextToken().charAt(0);
			char right = st.nextToken().charAt(0);
			
			makeTree(head, data, left, right);
		}
		
		preOrder(head);
		System.out.println();
		
		inOrder(head);
		System.out.println();
		
		postOrder(head);
	}
	private static void makeTree(Main.Node head, char data, char left, char right) {
		if(head.data == data) {
			if(left == '.') {
				head.leftNode = null;
			} else {
				Node leftNode = new Node(left);
				head.leftNode = leftNode;
			}
			
			if(right == '.') {
				head.rightNode = null;
			} else {
				Node rightNode = new Node(right);
				head.rightNode = rightNode;
			}
		} else {
			if(head.leftNode != null) {
				makeTree(head.leftNode, data, left, right);
			}
			if(head.rightNode != null) {
				makeTree(head.rightNode, data, left, right);
			}
		}
	}
}

 

제일 하단의

 

else {
    if(head.leftNode != null) {
        makeTree(head.leftNode, data, left, right);
    }
    if(head.rightNode != null) {
        makeTree(head.rightNode, data, left, right);
    }
}

위의 부분에서 순회하듯 자기 자신의 값을 찾을때 까지 순회를 먼저 한 후 

 

위의 if에서 자기자신 값을 찾으면 그때 왼쪽자식과 오른쪽 자식의 노드를 생성해 주면서 추가해 주는 부분이 있다.

 

위 부분만 조심하면 된다.

 

---

(Python 코드)

 

import sys
input = sys.stdin.readline

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

class Node:
    def __init__(self, data, leftNode, rightNode):
        self.data = data
        self.leftNode = leftNode
        self.rightNode = rightNode
        
def preOrder(node):
    print(node.data, end="")
    if node.leftNode != None:
        preOrder(tree[node.leftNode])
    if node.rightNode != None:
        preOrder(tree[node.rightNode])
        
def inOrder(node):
    if node.leftNode != None:
        inOrder(tree[node.leftNode])
    print(node.data, end="")
    if node.rightNode != None:
        inOrder(tree[node.rightNode])
        
def postOrder(node):
    if node.leftNode != None:
        postOrder(tree[node.leftNode])
    if node.rightNode != None:
        postOrder(tree[node.rightNode])
    print(node.data, end="")
        
for _ in range(n):
    data, left, right = map(str, input().split())
    if left == '.':
        left = None
    if right == '.':
        right = None
    tree[data] = Node(data, left, right)
    
preOrder(tree['A'])
print()
inOrder(tree['A'])
print()
postOrder(tree['A'])