자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(DFS_이진트리순회(DFS : Depth-First Search))

 

 

5. 이진트리순회(DFS : Depth-First Search)

 

 

이진 트리 구성

• 이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 계층적인 데이터 구조
• 데이터 검색, 정렬, 그래프 표현, 트리 순회 등 다양한 알고리즘에 활용된다.

1. 노드 (Node):
   • 이진 트리의 각 요소는 노드입니다.
   • 노드는 데이터와 두 개의 자식 노드에 대한 참조(포인터)로 구성됩니다.
   • 노드에 저장되는 데이터는 트리가 나타내는 문제나 데이터에 따라 다를 수 있습니다.
2. 루트 노드 (Root Node):
   • 이진 트리의 가장 상위 노드를 루트 노드라고 합니다.
   • 모든 경로는 루트 노드에서 시작하며, 트리의 시작점입니다.
3. 자식 노드 (Child Node):
   • 각 노드는 최대 두 개의 자식 노드를 가질 수 있습니다.
   • 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있습니다.
4. 부모 노드 (Parent Node):
   • 각 노드는 하나의 부모 노드를 가집니다. 부모 노드는 해당 노드를 직접 가리키는 노드입니다.
5. 리프 노드 (Leaf Node), 말단 노드:
   • 리프 노드는 어떤 자식 노드도 가지지 않는 노드로, 트리의 가장 끝 부분에 위치합니다.
6. 서브 트리 (Subtree):
   • 어떤 노드와 그 하위 모든 자식 노드로 구성된 트리를 서브 트리라고 합니다.
   • 이진 트리는 서브 트리로 계층적으로 구성됩니다.
7. 깊이 (Depth):
   • 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 에지(연결선)의 수를 노드의 깊이라고 합니다.
   • 루트 노드의 깊이는 0입니다.
8. 높이 (Height):
   • 트리의 높이는 트리에서 가장 깊은 노드의 깊이를 나타냅니다.
   • 리프 노드만을 자식으로 가지는 이진 트리의 높이를 리프 높이라고도 합니다.
9. 이진 트리 종류:
   • 완전 이진 트리 (Complete Binary Tree): 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리입니다.
   • 포화 이진 트리 (Full Binary Tree): 모든 노드가 0개 또는 2개의 자식 노드를 가지는 이진 트리입니다.

 

• 전위순회 출력 :  1 2 4 5 3 6 7 ( 부 -> 왼 -> 오 : 부모가 기준)

• 중위순회 출력 :  4 2 5 1 6 3 7  ( 왼 -> 부 -> 오 : 부모를 중간에 )

• 후위순위 출력 :  4 5 2 6 7 3 1  ( 왼 -> 오 -> 부 : 부모를 나중에 ) - 병합정렬에서 사용된다

 

class Node {
    int data;
    Node lt, rt; // 인스턴스 변수 : Node라는 클래스의 객체 주소를 저장
    public Node(int val) {
        data = val;
        lt=rt=null;
    }
}

public class Main {
    Node root;
    public void DFS(Node root) {
        if (root == null) return; // 말단 노드 일 경우
        else {
        // 함수 호출 2번 : 가지(왼쪽 오른쪽)
//            System.out.println(root.data+" "); // 전위 순회
            DFS(root.lt);
            System.out.println(root.data+" "); // 중위 순회
            DFS(root.rt);
//            System.out.println(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);
    }
}

tree.root변수가 -> root

new Node(1) 객체생성하면서 1번 루트 노드 생성

 

 

참고 링크 : 

https://kingpodo.tistory.com/27

5-2. [자료구조] 이진트리(binary tree)