자료구조 - [ 이진 트리 순회 ( 깊이 우선 / 너비 우선 ) ]

1. 깊이 우선 탐색

1) 전위 순회 (pre-order)

부모 노드를 선 방문 후 좌측 서브 트리와 우측 서브 트리를 방문하는 방법

void visit(Node node) {
    System.out.println(node.data);
}

void preOrder(Node parent) {
    if (null == parent) {
        return;
    }
    visit(parent);
    preOrder(parent.left);
    preOrder(parent.right);
}

 

 

---

2) 중위 순회 (in-order)

좌측 서브 트리를 방문하고 부모를 방문 후 우측 서브 트리를 방문하는 방법

void visit(Node node) {
    System.out.println(node.data);
}

void inOrder(Node parent) {
    if (null == parent) {
        return;
    }
    inOrder(parent.left);
    visit(parent);
    inOrder(parent.right);
}

 

 

---

3) 후위 순회 (post-order)

좌측 서브 트리를 방문하고 우측 서브 트리를 방문 후 부모를 방문하는 방법

void visit(Node node) {
    System.out.println(node.key);
}

void postOrder(Node parent) {
    if (null == parent) {
        return;
    }
    postOrder(parent.left);
    postOrder(parent.right);
    visit(parent);
}

 

 

 

---

2. 너비 우선 탐색

트리의 상위 레벨부터 하위 레벨까지 순차적으로 탐색해서 레벨 순회라고도 불린다.

깊이 우선 탐색에서는 스택 방식을 이용한 재귀적인 코드로 작성했으나 레벨 순회는 큐를 이용하여 순회한다.

1. 레벨 순회 방법은 다음과 같다.
2. 루트 노드를 큐에 삽입
3. 큐에 있는 노드를 꺼내 방문
4. 노드의 좌측 자식 노드를 큐에 삽입
5. 노드의 우측 자식 노드를 큐에 삽입
6. 큐가 비어있을 때 까지 2번 부터 반복

void visit(Node node) {
    System.out.println(node.key);
}

void levelOrder() {
    Queue<Node> queue = new LinkedList();
    if (null == root) {
        return;
    } 
    queue.offer(root);
    while(!queue.isEmpty()) {
        Node parent = queue.poll();
        visit(parent);
        if (null != parent.left) {
            queue.offer(parent.left);
        }
        if (null != parent.right) {
            queue.offer(parent.right);
        }
    }
}

 

 

---

참조

https://www.codelatte.io/courses/java_data_structure

자바 자료구조 강의 - 코드라떼