★이진트리순회(DFS)

스택의 구조를 익히는데 좋음!

 

전위순회 - 부모 -> 왼쪽자식 -> 오른쪽자식

중위순회 - 왼쪽자식 -> 부모 -> 오른쪽자식

후위순회 - 왼쪽자식 -> 오른쪽자식 -> 부모

 

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.lt = new Node(6);
        tree.root.rt.rt = new Node(7);
        tree.DFS(tree.root);
    }

}

/*1 2 4 5 3 6 7 */
/*4 2 5 1 6 3 7 */
/*4 5 2 6 7 3 1 */

 

root - 100번지

D(1) - 1 출력 D(2) 진입 D(3)남음

D(2) - 2 출력 D(4) 진입 D(5)남음

D(4) - 4 출력 왼쪽 D(null) 진입 오른쪽 D(null) 남음

null 일때 return; 오른쪽 D(null)진입 null 일때 return

D(5) - 5 출력 D(null) 진입 D(null) 남음

null 일때 return; 오른쪽 D(null)진입 null 일때 return

D(3) - 3 출력 D(6) 진입 D(7) 남음

null 일때 return; 오른쪽 D(null)진입 null 일때 return

D(6) - 6 출력 D(null) 진입 D(null) 남음

null 일때 return; 오른쪽 D(null)진입 null 일때 return

D(7) - 7 출력 D(null) 진입 D(null) 남음

null 일때 return; 오른쪽 D(null)진입 null 일때 return