[F-Lab 모각코 챌린지 21일차] Binary Tree 순회 방법과 구현

TIL

1. Binary Tree 순회 방법
2. 구현

 

---

 

Binary Tree 순회 방법

 

위 트리를 순회하는 방법은 3가지가 있다.
3가지 방법 다 루트노드를 기준으로 생각하고 그려보면 편하다.

1. 전위 순회
2. 중위 순회
3. 후위 순회
   
   

위 트리 구조를 기준으로 각 순회에 대해 알아보자.

 

 

 

 

전위 순회

1 -> 2 -> 3

• 루트노드 먼저 방문한다.

 

 

중위 순회

2 -> 1 -> 3

• 루트노드를 중간에 방문한다.

 

 

후위 순회

2 -> 3 -> 1

• 루트노드를 마지막에 방문한다.

 

 

이렇게 높이가 2 밖에 안 되는 이진트리는 내가 직접 하나하나 출력해도 상관없다.
근데 만약 트리의 높이가 늘어나면 어떻게 출력해야 할까? 그때도 내가 하나하나 직접 출력해야 할까?😑
위에서 순회한 각 방식을 하위 트리에도 재귀적으로 적용하는 코드를 작성하면 간단하게 출력할 수 있다.

 

 

 

 

해당 트리를 중위 순회해보자.

1. 중위 순회이므로 처음 방문하는 노드는 1번이 아닌 2번 노드이다.
2. 여기서 출력하려는데 2번 노드는 자식노드가 존재하므로 다시 재귀적인 중위 순회에 들어간다.
3. 4번 노드에 방문해 재귀적으로 중위 순회를 시도하지만!!! 자식노드가 없으므로 4가 출력된다.
4. 그리고 2가 출력되고 5가 출력된다.
   
   

2가 루트노드인 서브트리를 본다면 2가 중간에 출력되는 중위 순회가 잘 동작했다.
1이 루트노드인 전체 트리에서 본다면 왼쪽 서브트리는 순회를 다 마친 상태이다.

이제 루트노드의 data인 1을 출력하고 오른쪽 서브트리를 순회해보자.

 

5. 그럼 1이 출력된다.
6. 이제 3이 루트노드인 서브트리를 다시 중위 순회한다.
7. 먼저 6번노드를 방문한다.
8. 6번 노드에 방문해 재귀적으로 중위 순회를 시도하지만 자식노드가 없으므로 6이 출력된다.
9. 다음으로 3을 출력하고, 7을 출력한다.

 

이렇게 모든 노드가 재귀적으로 출력된다.
이 부분을 stack 구조에서 표현을 해보면(재귀 헷갈려서 그려봤다...🤦‍♀️)

 

 

해당 트리를 전위 순위해보면 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7
해당 트리를 후위 순위해보면 4 -> 2 -> 5 -> 6 -> 7 -> 3 -> 1

순서로 출력된다!

 

 

 

 

코드 구현

public class BinaryTree {
    private int data; // 저장 될 값
    private BinaryTree leftSubTree; // 왼쪽 자식노드의 참조
    private BinaryTree rightSubTree; // 오른쪽 자식노드의 참조

    BinaryTree(int data) {
        this.data = data;
    }

    public BinaryTree getLeftSubTree() {
        return leftSubTree;
    }

    public void setLeftSubTree(BinaryTree leftSubTree) {
        this.leftSubTree = leftSubTree;
    }

    public BinaryTree getRightSubTree() {
        return rightSubTree;
    }

    public void setRightSubTree(BinaryTree rightSubTree) {
        this.rightSubTree = rightSubTree;
    }

    // 전위순회로 트리 출력
    public void preOrderTraversal(BinaryTree tree) {
        if (tree == null) {
            return;
        }

        System.out.println(tree.data);
        this.preOrderTraversal(tree.getLeftSubTree());
        this.preOrderTraversal(tree.getRightSubTree());
    }

    // 중위순회로 트리 출력
    public void inOrderTraversal(BinaryTree tree) {
        if (tree == null) {
            return;
        }

        this.inOrderTraversal(tree.getLeftSubTree());
        System.out.println(tree.data);
        this.inOrderTraversal(tree.getRightSubTree());
    }

    // 후위순회로 트리 출력
    public void postOrderTraversal(BinaryTree tree) {
        if (tree == null) {
            return;
        }

        this.postOrderTraversal(tree.getLeftSubTree());
        this.postOrderTraversal(tree.getRightSubTree());
        System.out.println(tree.data);

    }

public static void main(String[] args) {

        BinaryTree tree1 = new BinaryTree(1);
        BinaryTree tree2 = new BinaryTree(2);
        BinaryTree tree3 = new BinaryTree(3);
        BinaryTree tree4 = new BinaryTree(4);
        BinaryTree tree5 = new BinaryTree(5);
        BinaryTree tree6 = new BinaryTree(6);
        BinaryTree tree7 = new BinaryTree(7);

        // tree 구조 만들기
        tree1.setLeftSubTree(tree2);
        tree1.setRightSubTree(tree3);

        tree2.setLeftSubTree(tree4);
        tree2.setRightSubTree(tree5);

        tree3.setLeftSubTree(tree6);
        tree3.setRightSubTree(tree7);

        // 각 순회 출력
        System.out.println("전위 순회: ");
        tree1.preOrderTraversal(tree1); // 1245367

        System.out.println("중위 순회: ");
        tree1.inOrderTraversal(tree1); // 4251637

        System.out.println("후위 순회: ");
        tree1.postOrderTraversal(tree1); // 4526731

    }

 

 

 

 

📚 참고
그림으로 쉽게 배우는 자료구조와 알고리즘(심화편)