Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

28. 트리

대표적인 그래프 종류 중 하나인 트리를 다뤄 봅시다.

Java / Python

4. 트리 순회

1991번

이진 트리에 대해 알아보고, 이진 트리를 순회해 봅시다.

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

전위 순회 : root -> l -> r
중위 순회 : l -> root -> r
후위 순회 : l -> r -> root

• Java

Node와 Tree class를 만들고 Node를 추가하고 탐색하는 함수와, 순회 함수들을 작성했다.

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

public class Main {
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	static class Node {
		char data;
		Node Left, Right;

		public Node(char data) {
			this.data = data;
		}
	}

	static class Tree {
		Node root; // 초기화 null 상태

		public void AddNode(char data, char leftData, char rightData) {
			if (root == null) { // 아무것도 없는 초기 상태 - A 루트 노드 생성
				root = new Node(data);

				// 좌우 값 존재시 노드 생성
				if (leftData != '.') {
					root.Left = new Node(leftData);
				}
				if (rightData != '.') {
					root.Right = new Node(rightData);
				}
			} else { // 초기상태가 아닌 경우 위치 찾기 - A 루트 노드 이후
				Search(root, data, leftData, rightData);
			}
		}

		public void Search(Node root, char data, char leftData, char rightData) {
			if (root == null) { // 도착 노드 null이면 재귀 종료 - 삽입할 노드 X
				return;
			} else if (root.data == data) { // 들어갈 위치
				if (leftData != '.') { // 값이 있는 경우만 좌우 노드 생성 (. - X)
					root.Left = new Node(leftData);
				}
				if (rightData != '.') {
					root.Right = new Node(rightData);
				}
			} else { // 탐색할 노드가 남아 있는 경
				Search(root.Left, data, leftData, rightData); // 왼쪽 재귀 탐색
				Search(root.Right, data, leftData, rightData); // 오른쪽 재귀 탐색
			}
		}

		// 전위순회 : 루트 -> 좌 -> 우
		public void PreOrder(Node root) throws IOException {
			bw.write(root.data); // 중
			if (root.Left != null)
				PreOrder(root.Left); // 왼쪽
			if (root.Right != null)
				PreOrder(root.Right); // 오른쪽
		}

		// 중위순회 : 좌 -> 루트 -> 우
		public void InOrder(Node root) throws IOException {
			if (root.Left != null)
				InOrder(root.Left); // 왼쪽 
			bw.write(root.data); // 중앙 
			if (root.Right != null)
				InOrder(root.Right); // 오른쪽
		}

		// 후위순회 : 좌 -> 우 -> 루트
		public void PostOrder(Node root) throws IOException {
			if (root.Left != null)
				PostOrder(root.Left); // 왼쪽 
			if (root.Right != null)
				PostOrder(root.Right); // 오른쪽
			bw.write(root.data); // 증
		}
	}

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

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

		Tree tree = new Tree();

		for (int i = 0; i < N; i++) {
			char[] data;
			data = br.readLine().replaceAll(" ", "").toCharArray();
			tree.AddNode(data[0], data[1], data[2]);
		}

		// 전위 순회
		tree.PreOrder(tree.root);
		bw.write("\n");

		// 중위 순회
		tree.InOrder(tree.root);
		bw.write("\n");

		// 후위 순회
		tree.PostOrder(tree.root);

		bw.flush();
		br.close();
		bw.close();
	}
}

• Python

import sys
input = sys.stdin.readline
N = int(input().strip())
tree = {}
 
for _ in range(N):
    root, left, right = input().strip().split()
    tree[root] = [left, right]

def preorder(root):
    if root != '.':
        print(root, end='')  # root
        preorder(tree[root][0])  # left
        preorder(tree[root][1])  # right


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


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


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