[BOJ] 백준 1991 트리순회

Approach

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

Tree 구조를 구현해서 아래 순서를 구현하는 문제이다.

• 전위 순회: Root → Left → Right

• 중위 순회: Left → Root → Right

• 후위 순회: Left → Right → Root

 

입력 데이터가 부모 - 자식 관계에 맞춰서 주어지기 때문에

트리를 구성해서 재귀방식으로 구현하면 된다.

---

C++

#include <stdio.h>

int N;
char parent, left, right;

typedef enum
{
    PRE_ORDER,
    IN_ORDER,
    POST_ORDER,
} TREE_ORDER;


struct
{
    char left, right;
} tree[27];


void treeTraversal(char ch, TREE_ORDER order)
{
    if (ch == '.') return;

    switch (order)
    {
    case PRE_ORDER: // 전위
        printf("%c", ch);
        treeTraversal(tree[ch].left, order);
        treeTraversal(tree[ch].right, order);
        break;

    case IN_ORDER: // 중위
        treeTraversal(tree[ch].left, order);
        printf("%c", ch);
        treeTraversal(tree[ch].right, order);
        break;

    case POST_ORDER: // 후위
        treeTraversal(tree[ch].left, order);
        treeTraversal(tree[ch].right, order);
        printf("%c", ch);
        break;
    default:
        break;
    }
}

int main()
{
    // freopen("input.txt", "r", stdin);

    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf(" %c %c %c", &parent, &left, &right);
        tree[parent].left = left;
        tree[parent].right = right;
    }

    // 전위
    treeTraversal('A', PRE_ORDER); puts("");

    // 중위
    treeTraversal('A', IN_ORDER); puts("");

    // 후위
    treeTraversal('A', POST_ORDER); puts("");
}

 

Java

import java.util.Scanner;

class Tree{
	String name;
	Tree left;
	Tree right;
	
	
	public void leftConnect(Tree target){
		this.left = target;
	}
	
	public void rightConnect(Tree target){
		this.right = target;
	}
	
	public void setName(String name){
		this.name = name;
	}
	
}

public class Main {
	public static void preOrder(Tree curTree) {
		if(curTree == null) {
			return;
		}
		System.out.print(curTree.name);
		preOrder(curTree.left);
		preOrder(curTree.right);
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = Integer.parseInt(sc.nextLine());
		Tree[] tree = new Tree[n];
		for (int i = 0; i < tree.length; i++) {
			tree[i] = new Tree();
		}
		for (int i = 0; i < n; i++) {
			String str = sc.nextLine();
			String[] temp = str.split(" ");
			int idx = temp[0].charAt(0)-65;
			
			tree[idx].setName(temp[0]);
			if(temp[1].equals("."))
				tree[idx].leftConnect(null);
			else{
				tree[idx].leftConnect(tree[temp[1].charAt(0)-65]);
			}
			if(temp[2].equals("."))
				tree[idx].rightConnect(null);
			else{
				tree[idx].rightConnect(tree[temp[2].charAt(0)-65]);
			}
		}
		
		Tree root = tree[0]; // 루트 노드 설정
		
		preOrder(root);
		System.out.println();
		inOrder(root);
		System.out.println();
		postOrder(root);
	}
	private static void inOrder(Tree curTree) {
		if(curTree == null) {
			return;
		}
		inOrder(curTree.left);
		System.out.print(curTree.name);
		inOrder(curTree.right);
	}
	private static void postOrder(Tree curTree) {
		if(curTree == null) {
			return;
		}
		postOrder(curTree.left);
		postOrder(curTree.right);
		System.out.print(curTree.name);
	}
}