Binary Tree_깊이 우선 탐색 DFS

✅ DFS: Depth First Search

Stack structure
Explore all subtree before going onto next

🆚 BFS: Breadth First Search

queue data
start at root, explore neighbors at present depth prior to moving on to next depth
move horizontal

출처: geeksforgeeks

✔️ 생성된 node의 lt, rt는 null

그래서 마지막으로 생성된 node는 값이 null
따라서 null값을 만나면 return하도록 한다.

✔️ 전위순회 Preorder Traversal

root > 왼쪽 > 오른쪽 부모 먼저 1 - 2 - 4 - 5 - 3 - 6 - 7

✔️ 중위순회 Inorder Traversal

왼쪽 > root > 오른쪽 부모 중간에 4 - 2 - 5 - 1 - 6 - 3 - 7

✔️ 후위순회 Postorder Traversal

왼쪽 > 오른쪽 > root 부모 마지막에 4 - 5 - 2 - 6 - 7 - 3 - 1 병합 정렬

✅ 깊이 탐색 위한 코드

class Node{
    int data; //field
    Node lt, rt; //instance field, type=node, saves the address of Node
    public Node(int value){ //constructor
        data=value;
        lt=rt=null;
    }
}
class Main {
    Node root;

    public void DFS(Node root){
        if(root==null) return;
        else{
            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); //call function
    }
}

🔵 ThingsILearned

⭐️ Node Class ✔️ data라는 int필드 설정, 여기에 1,2,3등 들어갈 것
✔️ Node type의 lt, rt 여기에 Node의 주소 저장
✔️ 생성자, Node가 새로 만들어지면 lt, rt 값은 null로 초기화된다.

⭐️ DFS ✔️ 함수 호출이 일어나는 것이 바로 가지 뻗기
✔️ Node가 null값이면 멈춘다.

⭐️ 실행함수 ✔️ main class를 부르고
✔️ root부터 노드 정해줌
✔️ root 의 lt, rt를 뻗어나가며 노드 저장
✔️ 마지막으로 메인 클래스의 DFS클래스를 실행하고, 처음에 만든 root를 parameter로 전달

🟢 전위 순회

class Node{
    int data; //field
    Node lt, rt; //instance field, type=node, saves the address of Node
    public Node(int value){ //constructor
        data=value;
        lt=rt=null;
    }
}
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); //call function
    }
}

//⭐️output:
1 2 4 5 3 6 7

🟢 중위 순회

class Node{
    int data; //field
    Node lt, rt; //instance field, type=node, saves the address of Node
    public Node(int value){ //constructor
        data=value;
        lt=rt=null;
    }
}
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); //call function
    }
}


//⭐️output:
4 2 5 1 6 3 7

🟢 후위 순회

class Node{
    int data; //field
    Node lt, rt; //instance field, type=node, saves the address of Node
    public Node(int value){ //constructor
        data=value;
        lt=rt=null;
    }
}
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); //call function
    }
}


//⭐️output:
4 5 2 6 7 3 1