이진트리순회 : 깊이우선탐색(DFS : Depth-fist Search)

이진트리 순회에 대한 이미지

- 기본적으로 왼쪽에서 오른쪽으로 순회

 

전위순회 : 부모노드가 맨 앞 위치

중위순회 : 부모노드가 중간 위치

후위순회 : 부모노드가 맨 뒤 위치

 

- 2022.01.23

import java.util.*;

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


public class Main {
    Node root;
    public void DFS(Node root){
        // 전위순회
        if(root == null){
            return;
        }else{
            System.out.print(root.data + " ");
            DFS(root.lt);
            DFS(root.rt);
        }
        // 중위순회
        if(root == null){
            return;
        }else{
            DFS(root.lt);
            System.out.print(root.data + " ");
            DFS(root.rt);
        }
        // 후위순회
        if(root == null){
            return;
        }else{
            DFS(root.lt);
            DFS(root.rt);
            System.out.print(root.data + " ");
        }
    }

    public static void main(String args[]){
        Main tree = new Main();
        tree.root = new Node(1);
        tree.root.lt = new Node(2);
        tree.root.rt = new Node(3);
        tree.root.lt.lt = new Node(4);
        tree.root.lt.rt = new Node(5);
        tree.root.rt.lt = new Node(6);
        tree.root.rt.rt = new Node(7);
        tree.DFS(tree.root);
    }

}

- 연습 코드

import java.util.*;

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

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

}