[PS] 인프런 강의 - Tree 1.이진트리 순회(깊이우선탐색 DFS)

 

문제

아래 그림과 같은 이진트리를 전위순회와 후위순회를 연습해보세요.

전위순회 출력 : 1 2 4 5 3 6 7
중위순회 출력 : 4 2 5 1 6 3 7
후위순회 출력 : 4 5 2 6 7 3 1

풀이

생략

코드

import java.util.Scanner;

class Node{
	int data;
	Node lt, rt;
	
	public Node(int val) {
		data = val;
		lt = rt = null;
	}
}

public class Main {

	//전위 순회
	public static void DFS(Node root) {
		if(root == null) return;
		else {
			System.out.print(root.data + " ");
			DFS(root.lt);
			DFS(root.rt);
		}
	}
	
	//중위 순회
	public static void DFS2(Node root) {
		if(root == null) return;
		else {
			DFS2(root.lt);
			System.out.print(root.data + " ");
			DFS2(root.rt);
		}
	}
	
	//후위 순회
	public static void DFS3(Node root) {
		if(root == null) return;
		else {
			DFS3(root.lt);
			DFS3(root.rt);
			System.out.print(root.data + " ");
		}
	}
	
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        
        Node root = new Node(1);
        root.lt = new Node(2);
        root.rt = new Node(3);
        
        root.lt.lt = new Node(4);
        root.lt.rt = new Node(5);
       
        root.rt.lt = new Node(6);
        root.rt.rt = new Node(7);
        
        DFS(root);
        System.out.println("");
        DFS2(root);
        System.out.println("");
        DFS3(root);
    }
}