이진 트리 순회

트리 순회 방식

---

1. 전위 순회
   •  부모 -> 왼쪽 -> 오른쪽 순으로 순회한다.
   • 1-2-4-5-3-6-7
2. 중위 순회
   • 왼쪽 -> 부모 -> 오른쪽 순으로 순회한다.
   • 4-2-5-1-6-3-7
3. 후위 순회
   • 왼쪽 -> 오른쪽 -> 부모 순으로 순회한다.
   • 4-5-2-6-7-3-1

 

코드 구현

---

data = node로 생각하면 된다.

 

DFS_전위 순회

public class Solution {
    Node root;
    public void DFS(Node root){
        if(root==null) return;
        else {
            System.out.print(root.data+ " -> ");      //전위 순회 출력
            DFS(root.lt);   //트리 왼쪽으로 값 전달 | (root.lt).lt (root.lt.lt).lt
//            System.out.print(root.data+ " -> ");      //중위 순회 출력
            DFS(root.rt);   //트리 오른쪽으로 값 전달
//            System.out.print(root.data+ " -> ");      //후위 순회 출력
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        sol.root = new Node(1);
        sol.root.lt = new Node(2);
        sol.root.rt = new Node(3);
        sol.root.lt.lt = new Node(4);
        sol.root.lt.rt = new Node(5);
        sol.root.rt.rt = new Node(6);
        sol.root.rt.lt = new Node(7);
        sol.DFS(sol.root);
    }
}
class Node{
    int data;
    Node lt, rt;        //Node의 객체 주소를 저장
    public Node(int val){
        data = val;
        lt = rt = null;
    }
}