이것저것 해보기🌼

[백준 온라인 저지] 1991번: 트리 순회 본문

코딩테스트

[백준 온라인 저지] 1991번: 트리 순회

realtree 2021. 7. 2. 13:45

유형 : 이진트리

 

Tree의 순회 알고리즘 3개 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal) 를 구현하는 문제다.

전체 트리를 생성하는 부분도 구현해야 하므로 기본적인 이진트리 공부에 좋은 문제다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import java.io.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Node{
    char c;
    Node left;
    Node right;
    Node(char data){
        this.c = data;
    }
}
class Tree{
    Node root;
    public void createTree(char data, char leftdata, char rightdata) {
        if(root == null) {
            root = new Node(data);
        
        if(leftdata != '.') {
            root.left = new Node(leftdata);
        }
        if(rightdata != '.') {
            root.right = new Node(rightdata);
        }
        }
        else {
            searchTree(root, data, leftdata,rightdata);
        }
    }
    public void searchTree(Node ptr, char a, char b, char c) {
        if(ptr.c == a) {
            if(b!='.')
                ptr.left = new Node(b);
            if(c!='.')
                ptr.right = new Node(c);
        }
        else {
            if(ptr.left != null)
                searchTree(ptr.left, a,b,c);
            if(ptr.right != null)
                searchTree(ptr.right, a, b,c);
        }
    }
    
    //pre
    public void preorder(Node node) {
        System.out.print(node.c);
        if(node.left != null)
            preorder(node.left);
        if(node.right != null)
            preorder(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.c);
    }
    public void inorder(Node node) {
        if(node.left != null)
            inorder(node.left);
        System.out.print(node.c);
        if(node.right != null)
            inorder(node.right);
    }
}
 
public class Main {
 
    public static void main(String[] args) {
        int n;
        int cnt = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            Tree tree = new Tree();
            n = Integer.parseInt(br.readLine());
            for(int i=0; i<n; i++) {
                String sr = br.readLine();
                String[] split = sr.split(" ");
                
                char a = split[0].charAt(0);
                char b = split[1].charAt(0);
                char c = split[2].charAt(0);
                tree.createTree(a,b,c);
                
            }
            
            tree.preorder(tree.root);
            System.out.println();
 
            tree.inorder(tree.root);
            System.out.println();
 
            tree.postorder(tree.root);
            System.out.println();
            
        }
        catch(IOException e) {
            
        }
    }
}
 
cs

 

 

문제링크 : https://www.acmicpc.net/problem/1991

 

1991번: 트리 순회

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자

www.acmicpc.net

 

'코딩테스트' 카테고리의 다른 글

[프로그래머스] 송전탑 분할  (0) 2021.07.11
[자료구조] List, Map, Set, Stack, Queue 연습 (JAVA)  (0) 2021.07.02
[SQL] postgreSQL 문법 정리(CASE,JOIN,GROUP BY등)  (0) 2021.07.02
[DFS/BFS/백트래킹] 참고자료, 코드  (0) 2021.07.02
[구름] 코딩테스트 대비 JAVA BufferedReader 사용법  (0) 2021.07.02
'코딩테스트' Related Articles more