[DFS - 깊이우선탐색] 이진트리 순회 .java

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

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

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

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

 

 

내 풀이

부모 기준으로 제일 먼저면 전위, 두번째면 중위, 마지막으로 방문하면 후위이

• 전위순회 : 부모 -> 왼쪽 자식 -> 오른쪽 자식
• 중위순회: 왼쪽 자식 -> 부모 -> 오른쪽 자식
• 후위 순회: 왼쪽 자식 -> 오른쪽 자식 -> 부모  => 병합정렬에 많이 쓰임

100으로 시작하는 건 주소이다

0으로 적은 건 null을 대신해서 표현한것

위 그림의 트리를 코드로 표현하기 위한 설명이다

 

 

 

전위 순회

부모 먼저 출력하고 왼 -> 오

import java.util.Scanner;
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);//오른쪽
            }
	}
    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.Scanner;
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 {
                dfs(root.lt);//왼쪽부터 
                System.out.print(root.data + " ");
                    dfs(root.rt);//오른쪽
            }
	}
    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.Scanner;
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 {
                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);//루트 노드 넘기기

        
    }

    
}