[1991] 트리 순회

기본적인 트리 문제였다. 하지만 제일 먼저 떠오른건 이차원 배열로 푸는 방법...

트리를 구현해서 다시 풀어봐야겠다.

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
        // [][0] : 왼쪽 자식 노드, [][1] : 오른쪽 자식 노드
		int[][] arr = new int[n][2];
		
		for(int i=0; i<n; i++) {
			char a = sc.next().charAt(0); char b = sc.next().charAt(0); char c = sc.next().charAt(0);
			// A가 0으로 되게 처리
            arr[a - 'A'][0] = b - 'A';
			arr[a - 'A'][1] = c - 'A';
		}
		
		preorder(0, arr);
		System.out.println();
		inorder(0, arr);
		System.out.println();
		postorder(0, arr);
	}

	public static void preorder(int s, int[][] arr) {
    	// 출력시 문자로 다시 바꿔주는 작업
		System.out.print((char)(s + 'A'));
		for(int i=0; i<2; i++) {
        // .의 아스키코드값은 -19
			if(arr[s][i] != -19) {
				preorder(arr[s][i], arr);
			}
		}
	}
	
	public static void inorder(int s, int[][] arr) {
		if(arr[s][0] != -19) {
			inorder(arr[s][0], arr);
		}
    	// 출력시 문자로 다시 바꿔주는 작업
		System.out.print((char)(s + 'A'));
        // .의 아스키코드값은 -19
		if(arr[s][1] != -19) {
			inorder(arr[s][1], arr);
		}
	}
	
	public static void postorder(int s, int[][] arr) {
		for(int i=0; i<2; i++) {
        // .의 아스키코드값은 -19
			if(arr[s][i] != -19) {
				postorder(arr[s][i], arr);
			}
		}
    	// 출력시 문자로 다시 바꿔주는 작업
		System.out.print((char)(s + 'A'));
	}
}

 

+ 추가
노드로 푼 코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		Tree tree = new Tree();
		for(int i=0; i<n; i++) {
			String data = sc.next(); String left = sc.next(); String right = sc.next();
			tree.addNode(tree, data, left, right);
		}
		
		tree.preorder(tree.root);
		System.out.println();
		tree.inorder(tree.root);
		System.out.println();
		tree.postorder(tree.root);
	}
}

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

class Tree{
	Node root;
	
	public Tree() {
		
	}
	
	public void addNode(Tree t, String data, String left, String right) {
		if(t.root == null) {
			Node node = new Node(data);
			root = node;
			if(left != ".")
				root.left = new Node(left);
			if(right != ".")
				root.right = new Node(right);
		} else {
			searchNode(root, data, left, right);
		}
	}
	
	public void searchNode(Node node, String data, String left, String right) {
		if(node == null) {
			return ;
		}
		if(!node.data.equals(data)) {
			searchNode(node.left, data, left, right);
			searchNode(node.right, data, left, right);
		} else if(node.data.equals(data)) {
			if(left != ".")
				node.left = new Node(left);
			if(right != ".")
				node.right = new Node(right);
		}
	}
	
	public void preorder(Node start) {
		if(start != null && !start.data.equals(".")) {
			System.out.print(start.data);
			if(start.left != null && !start.left.data.equals("."))
				preorder(start.left);
			if(start.right != null && !start.right.data.equals("."))
				preorder(start.right);
		}
	}
	public void inorder(Node start) {
		if(start != null && !start.data.equals(".")) {
			if(start.left != null && !start.left.data.equals(".")) {
				inorder(start.left);
			}
			System.out.print(start.data);
			if(start.right != null && !start.right.data.equals("."))
				inorder(start.right);
		}
	}
	public void postorder(Node start) {
		if(start != null && !start.data.equals(".")) {
			if(start.left != null && !start.left.data.equals("."))
				postorder(start.left);
			if(start.right != null && !start.right.data.equals(".")) {
				postorder(start.right);
			}
			System.out.print(start.data);
		}
	}
}