'Do it 자료구조와 함께 배우는 알고리즘 입문' 도서를 토대로 공부하고 관련한 문제를 찾아풀어보고 있습니다.

'이진 트리' 자료구조 문제 풀이입니다!!!

문제

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

[나의 풀이]

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

// 노드 클래스
class Node {
	
    // 노드의 데이터
    String data;
    
    // 왼쪽 노드
    Node left;
    
    // 오른쪽 노드
    Node right;

    Node (String data){
        this.data = data;
    }

}

// 이진 트리 클래스
class BinaryTree {
	
    // 최상위 루트 : root
    Node root;
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	// 새 노드 생성
    void createNode(String data, String leftdata, String rightdata){
		
        // root가 비어있으면 root에 삽입
        if (root == null)
        {
            root = new Node(data);  
            if (!leftdata.equals(".")){
                root.left = new Node(leftdata);
            }
            if (!rightdata.equals(".")){
                root.right = new Node(rightdata);
            }

        }
        // root가 비어있지 않다면 어떤 노드에 삽입할지 탐색
        else {
            searchNode(root, data, leftdata, rightdata);
        }
    }
	
    // 삽입할 노드 위치 탐색
    void searchNode(Node node, String data, String leftdata, String rightdata){
		
        // 삽입할 위치가 없으면 return
        if (node == null){

            return;

        }
        
        // 삽입할 위치를 찾으면 노드 삽입
        else if (node.data.equals(data)){

            if (!leftdata.equals(".")){
                node.left = new Node(leftdata);
            }
            if (!rightdata.equals(".")){
                node.right = new Node(rightdata);
            }
        }
        else{
			
            // 왼쪽 탐색
            searchNode(node.left, data, leftdata, rightdata);
            // 오른쪽 탐색
            searchNode(node.right, data, leftdata, rightdata);

        }

    }
	
    // 전위 탐색
    // root - left - right
    void preOrder(Node node) throws IOException{
        
        if (node != null){
            bw.write(node.data+"");
            bw.flush();
            if (node.left != null){
                preOrder(node.left);
            }
            if (node.right != null){
                preOrder(node.right);
            }
        }

    }
	
    // 중위 탐색
    // left - root -right
    void inOrder(Node node) throws IOException{

        if (node != null){

            if (node.left != null){
                inOrder(node.left);
            }
            bw.write(node.data+"");
            bw.flush();
            if (node.right != null){
                inOrder(node.right);
            }
        }

    }
	
    // 후위 탐색
    // left - right - root
    void postOrder(Node node) throws IOException{

        if (node != null){
            
            if(node.left != null){
                postOrder(node.left);
            }
            if(node.right != null){
                postOrder(node.right);
            }
            bw.write(node.data+"");
            bw.flush();
        }

    }

}


public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        BinaryTree binaryTree = new BinaryTree();
        
        String a;
        String b;
        String c;

        for (int i=0; i<N; i++){
            
            st = new StringTokenizer(br.readLine());
            a = st.nextToken();
            b = st.nextToken();
            c = st.nextToken();
            binaryTree.createNode(a, b, c);
        }

        binaryTree.preOrder(binaryTree.root);
        bw.write("\n");
        bw.flush();
        binaryTree.inOrder(binaryTree.root);
        bw.write("\n");
        bw.flush();
        binaryTree.postOrder(binaryTree.root);

    }
}

이진 트리 구조에서의 전위 순회, 중위 순회, 후위 순회 문제입니다. 노드 클래스, 이진 트리 클래스를 정의하여 이진 트리 자료구조를 구현하였습니다. 또한 root -left-right 순으로 순회하는 전위 순회, left-root-right 순으로 순회하는 중위 순회, left-right-root 순으로 순회하는 후위 순회 메소드들을 구현하여 해결하였습니다. 🐇🐇🐇

감사합니다.🏃🏃🏃