[백준/자료구조 - 트리] 1991: 트리 순회

문제

---

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

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{
	char data;
	Node left;
	Node right;
	
	Node(char data, Node left, Node right){
		this.data = data;
		this.left = left;
		this.right = right;
	}
}

public class Main {
	static StringTokenizer st;
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static Node root = new Node('A', null, null);
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		
		for(int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			char data = st.nextToken().charAt(0);
			char leftData = st.nextToken().charAt(0);
			char rightData = st.nextToken().charAt(0);
			addNode(root, data, leftData, rightData);
		}

		preOrder(root);
		bw.write("\n");
		inOrder(root);
		bw.write("\n");
		postOrder(root);
		bw.write("\n");
		bw.flush();
		bw.close();
	}
	
	public static void addNode(Node node, char data, char left, char right) {
		if(node.data != data) {
			if(node.left != null) addNode(node.left, data, left, right);
			if(node.right != null) addNode(node.right, data, left, right);
		} else {
			if(left == '.') node.left = null;
			else node.left = new Node(left, null, null);
			if(right == '.') node.right = null;
			else node.right = new Node(right, null, null);
		}
		
	}
	
	public static void preOrder(Node root) throws IOException {
		if(root == null) return;
		bw.write(root.data);
		preOrder(root.left);
		preOrder(root.right);
	}
	
	public static void inOrder(Node root) throws IOException {
		if(root == null) return;
		inOrder(root.left);
		bw.write(root.data);
		inOrder(root.right);
	}
	
	public static void postOrder(Node root) throws IOException {
		if(root == null) return;
		postOrder(root.left);
		postOrder(root.right);
		bw.write(root.data);
	}
}

 

또 다른풀이 (트리 구현)

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

class Node {
	char data;
	Node left;
	Node right;
	
	Node(char data){
		this.data = data;
	}
}

class Tree{
	public Node root;
	
	public void initAddNode(char data, char leftData, char rightData) {
		if(root == null) {
			if(data != '.') root = new Node(data);
			if(leftData != '.') root.left = new Node(leftData);
			if(rightData != '.') root.right = new Node(rightData);
		} else {
			searchInput(root, data, leftData, rightData);
		}	
	}
	
	public void searchInput(Node root, char data, char leftData, char rightData) {
		if(root == null) {
			return;
		} else if(root.data == data) {
			if(leftData != '.') root.left = new Node(leftData);
			if(rightData != '.') root.right = new Node(rightData);
		} else {
			searchInput(root.left, data, leftData, rightData);
			searchInput(root.right, data, leftData, rightData);
		}
	}
	
	public void preOrder(Node root) {
		System.out.print(root.data);
		if(root.left != null) preOrder(root.left);
		if(root.right != null) preOrder(root.right);
	}
	
	public void inOrder(Node root) {
		if(root.left != null) inOrder(root.left);
		System.out.print(root.data);
		if(root.right != null) inOrder(root.right);
	}
	
	public void postOrder(Node root) {
		if(root.left != null) postOrder(root.left);
		if(root.right != null) postOrder(root.right);
		System.out.print(root.data);
	}
}

public class Main {
	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++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			char data = st.nextToken().charAt(0);
			char leftData = st.nextToken().charAt(0);
			char rightData = st.nextToken().charAt(0);
			tree.initAddNode(data, leftData, rightData);
		}
		
		tree.preOrder(tree.root);
		System.out.println();
		
		tree.inOrder(tree.root);
		System.out.println();
		
		tree.postOrder(tree.root);
		System.out.println();
	}
}